hihoCoder #1143 : 骨牌覆盖问题·一(矩阵乘法)

本文主要是介绍hihoCoder #1143 : 骨牌覆盖问题·一(矩阵乘法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1143 : 骨牌覆盖问题·一

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：
我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？
举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：
week41_1.PNG
提示：骨牌覆盖
提示：如何快速计算结果
输入
第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000
输出
第1行：1个整数，表示覆盖方案数 MOD 19999997
样例输入
62247088
样例输出
17748018

/*
递推式:f[i]=f[i-1]+f[i-2].
然后就是斐波那契了... 
*/
#include<iostream>
#include<cstdio>
#define mod 19999997
#define LL long long
using namespace std;
LL n,ans[3][3],b[3][3],c[3][3];
void mi()
{while(n){if(n&1){for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)c[i][j]=(c[i][j]+ans[i][k]*b[k][j]%mod)%mod;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)ans[i][j]=c[i][j],c[i][j]=0;}for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)b[i][j]=c[i][j],c[i][j]=0;n>>=1;}
}
void slove()
{n--;ans[1][1]=2,ans[1][2]=1;b[1][1]=b[1][2]=b[2][1]=1;mi();cout<<ans[1][2];
}
int main()
{cin>>n;slove();return 0;
}