题目：http://hihocoder.com/contest/hiho41/problem/1
题目1 : 骨牌覆盖问题·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：
我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？
举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：
输入
第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000
输出
第1行：1个整数，表示覆盖方案数 MOD 19999997
- 样例输入
-
62247088
- 样例输出
-
17748018
可能会因为编译器版本问题，long long 会报错，可以使用 __int64进行替代
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 #define modnum 19999997 5 typedef vector<long long> matrow; 6 typedef vector<matrow> mat; 7 mat build(long long x,long long y,long long a[]) 8 { 9 mat ans; 10 for(long long i=0;i<x;i++) 11 { 12 ans.push_back(matrow()); 13 for(long long j=0;j<y;j++) 14 { 15 ans[i].push_back(a[i*y+j]); 16 } 17 } 18 return ans; 19 } 20 mat multi(const mat mat1,const mat mat2) 21 { 22 long long temp=0; 23 long long rownum=mat1.size(); 24 long long colnum=mat2[0].size(); 25 long long nummul=mat1[0].size(); 26 mat ans; 27 for(long long i=0;i<rownum;i++) 28 { 29 ans.push_back(matrow()); 30 for(long long j=0;j<colnum;j++) 31 { 32 temp=0; 33 for(long long t=0;t<nummul;t++) 34 temp+=mat1[i][t]*mat2[t][j]; 35 ans[i].push_back(temp%modnum); 36 } 37 } 38 return ans; 39 } 40 41 int main() 42 { 43 long long N; 44 long long a[]={1,1,1,2}; 45 long long b[]={1,2}; 46 cin>>N; 47 mat ans=build(2,1,b); 48 mat temp=build(2,2,a); 49 long long n=(N+1)/2-1; 50 if(N==1)cout<<1<<endl; 51 if(N==2)cout<<2<<endl; 52 if(N!=1&&N!=2) 53 while(n) 54 { 55 if(n&1==1) 56 ans=multi(temp,ans); 57 temp=multi(temp,temp); 58 n=n>>1; 59 } 60 if(N%2==1) 61 cout<<ans[0][0]<<endl; 62 else 63 cout<<ans[1][0]<<endl; 64 return 0; 65 }