这个题目也是很不容易啊，一直坚持不懈的推了一天，终于自己写出来了
题意很简单这里就不说了
其实我们发现对于每个n只有5种结尾的情况，所以开始就想从这5个情况中找突破口
结果发现要么会算重要么会算少
然后就找了16种状态，就是最后一列的状态，结果16个dp方程把我推得晕头转向的
最后想到，我们关心的就是把最后那五种情况的和而已
而这五种情况可以由那16种情况中的五种推出来，然后慢慢推，发现那16种情况中只有6个跟最终的结果相关
然后就是有递推式，用矩阵快速幂加速一下就好了
下面放上AC代码
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #define ll long long using namespace std; const ll mod=1000000007; struct matrix { ll m[10][10]; }; matrix multi(matrix a, matrix b) { matrix tmp; for (int k=1;k<=6;k++) for (int j=1;j<=6;j++) tmp.m[k][j]=0; for(int i = 1; i <=6; ++i) //55是base的范围 { for(int j = 1; j<=6; ++j) { for(int k = 1; k <=6; ++k) tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % mod; } } return tmp; } matrix fast_mod(matrix base, ll m) // 求矩阵 base 的m次幂 n为base的范围 { matrix ans; for (int k=1;k<=6;k++) for (int j=1;j<=6;j++) ans.m[k][j]=0; for(int i = 1; i <= 6; i++) ans.m[i][i] = 1; while(m) { if(m & 1) //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t ans = multi(ans, base); base = multi(base, base); m >>= 1; } return ans; } int main() { matrix a,b; a.m[1][1]=1;a.m[1][2]=1;a.m[1][3]=1;a.m[1][4]=1;a.m[1][5]=1;a.m[1][6]=0; a.m[2][1]=1;a.m[2][2]=0;a.m[2][3]=0;a.m[2][4]=0;a.m[2][5]=0;a.m[2][6]=1; a.m[3][1]=1;a.m[3][2]=0;a.m[3][3]=0;a.m[3][4]=0;a.m[3][5]=0;a.m[3][6]=0; a.m[4][1]=1;a.m[4][2]=0;a.m[4][3]=0;a.m[4][4]=0;a.m[4][5]=1;a.m[4][6]=0; a.m[5][1]=1;a.m[5][2]=0;a.m[5][3]=0;a.m[5][4]=1;a.m[5][5]=0;a.m[5][6]=0; a.m[6][1]=0;a.m[6][2]=1;a.m[6][3]=0;a.m[6][4]=0;a.m[6][5]=0;a.m[6][6]=0; ll n; while(~scanf("%lld",&n)) { if (n==1) {printf("1\n");continue;} else if (n==2) {printf("5\n");continue;} n-=2; ll aa,bb,cc,dd,ee,ff; aa=5;bb=1;cc=1;dd=2;ee=2;ff=1; b=fast_mod(a,n); /* for (int k=1;k<=6;k++) { for(int j=1;j<=6;j++) cout<<b.m[k][j]<<" "; cout<<endl; }*/ aa=((b.m[1][1]*aa)%mod+(b.m[2][1]*bb)%mod+(b.m[3][1]*cc)%mod+(b.m[4][1]*dd)%mod+(b.m[5][1]*ee)%mod+(b.m[6][1]*ff)%mod)%mod; printf("%lld\n",aa); } return 0; }