#1143 : 骨牌覆盖问题·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：
我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？
举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：
输入
第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000
输出
第1行：1个整数，表示覆盖方案数 MOD 19999997
- 样例输入
-
62247088
- 样例输出
-
17748018 如果最左边竖着放，那么方法数等于f（n-1）
如果最左边横着放，放么方法数等于f（n-2）
所以f（n）=f（n-1）+f（n-2）
矩阵快速幂#include<cstdio>
#include<cstring>
#define mod 19999997
using namespace std;
long long a[][],ans[][],tmp[][];
long long n;
void mul(long long s1[][],long long s2[][])
{
memset(tmp,,sizeof(tmp));
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
tmp[i][j]=(tmp[i][j]+s1[i][k]*s2[k][j])%mod;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
s1[i][j]=tmp[i][j];
}
void solve()
{
for(;n;n>>=,mul(a,a))
if(n&) mul(ans,a);
printf("%lld\n",ans[][]);
}
int main()
{
scanf("%lld",&n);
if(n==)
{
printf("0\n");
return ;
}
a[][]=;a[][]=;
a[][]=;a[][]=;
ans[][]=; ans[][]=;
solve();
}