1618: 骨牌覆盖1
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 378 Solved: 180
[Submit][Status][Web Board]
Description
?我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？
Input
输入n，n<=100000
Output
覆盖方案总数对19999997取余
Sample Input
1
2
Sample Output
1
2
分析：
-
找到规律后其实就是求斐波那契数列咯，然后只是这里n会很大，如果递归或者枚举的话会很麻烦，所以用到了矩阵;
-
对于 Fibonacci 数列，我们希望找到一个2x2的矩阵M，使得(a, b) x M = (b, a+b)，其中(a, b)和(b, a+b)都是1x2的矩阵。显然，只要 M = [0, 1; 1, 1]；
-
接下来，找规律！
即可得到第n项的公式；
当我看到绿色的Accept的时候！！可以说是爆炸开心了！！！
代码：
#include<bits/stdc++.h>
using namespace std;
const int NUM = 19999997; void cal(long long a[2][2],long long b[2][2])//a用来储存前面的矩阵，b用来存储中间的矩阵
{long long c[2][2];//c是等号后面的矩阵 c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%NUM;c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%NUM;c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%NUM;c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%NUM;a[0][0]=c[0][0];//将c再赋值给a a[0][1]=c[0][1];a[1][0]=c[1][0];a[1][1]=c[1][1];}
int main()
{long int n,cnt=0;//cin>>n;while(scanf("%lld",&n)!=EOF){long long a[2][2]={1,0,0,1};long long m[2][2]={0,1,1,1};//cout<<m[2][2]<<endl;if(n==2){cout<<"2\n";}else {while(n--){cal(a,m);}cout<<a[1][1]<<endl;}}return 0;}