hihoCoder 1151 : 骨牌覆盖问题・二 矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET

hihoCoder 1151 : 骨牌覆盖问题・二 矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET

#1151 : 骨牌覆盖问题・二

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

上一周我们研究了2xN的骨牌问题，这一周我们不妨加大一下难度，研究一下3xN的骨牌问题？
所以我们的题目是：对于3xN的棋盘，使用1x2的骨牌去覆盖一共有多少种不同的覆盖方法呢？
首先我们可以肯定，奇数长度一定是没有办法覆盖的；对于偶数长度，比如2，4，我们有下面几种覆盖方式：

提示：3xN骨牌覆盖

输入

第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000

输出

第1行：1个整数，表示覆盖方案数 MOD 12357

样例输入

62247088

样例输出

4037

//同1，但是起始的向量和矩阵都变化了，详细可以看hihocoder的说明； 

Read full article from hihoCoder 1151 : 骨牌覆盖问题・二 矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET