由于棋盘只有两行，所以如果第i列的骨牌竖着放，那么就转移为第1列到第i-1列骨牌有多少种摆法
如果第一行第i列骨牌横着放，那么第二行第i列也要横着放，那么就转移为了第1列到第i-2列骨牌有多少种方法
dp[i] = dp[i-1] + dp[i-2],但是列数太多了。 这种递推的算式可以用矩阵快速幂来优化
所以时间复杂度瞬间变为O(logn)
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 typedef long long LL; 15 const int INF = 1<<30; 16 LL ans; 17 const int MOD = 19999997; 18 //矩阵快速幂 a[i] = a[i-1] + a[i-2] 19 20 struct Matrix 21 { 22 LL m[2][2]; 23 }; 24 Matrix operator*(const Matrix &lhs, const Matrix &rhs) 25 { 26 Matrix ret; 27 for(int i=0; i<2; ++i) 28 for(int j=0; j<2; ++j) 29 ret.m[i][j] = 0; 30 for(int i=0; i<2; ++i) 31 for(int j=0; j<2; ++j) 32 for(int k=0; k<2; ++k) 33 if(lhs.m[i][k]!=0 && rhs.m[k][j]!=0) 34 ret.m[i][j] = (ret.m[i][j] + lhs.m[i][k] * rhs.m[k][j])%MOD; 35 36 return ret; 37 } 38 Matrix operator^(Matrix a, int k) 39 { 40 Matrix ret; 41 for(int i=0; i<2; ++i) 42 for(int j=0; j<2; ++j) 43 ret.m[i][j] = 1; 44 ret.m[1][1] = 0; 45 while(k) 46 { 47 if(k&1) 48 ret = ret * a; 49 k>>=1; 50 a = a * a; 51 } 52 return ret; 53 } 54 55 int main() 56 { 57 int n; 58 while(scanf("%d",&n)!=EOF) 59 { 60 Matrix tmp; 61 for(int i=0; i<2; ++i) 62 for(int j=0; j<2; ++j) 63 tmp.m[i][j] = 1; 64 tmp.m[1][1] = 0; 65 Matrix final = tmp ^ (n-3); 66 LL ans = (2 * final.m[0][0] + 1 * final.m[1][0])%MOD; 67 printf("%lld ",ans); 68 } 69 return 0; 70 }