手推一下发现每6个为一节，然后就能构造出矩阵，然后就是矩阵快速幂了。下面给代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> typedef long long ll; using namespace std; const int MOD=1e9+7; int n=7; ll b[20][20]={ {13,8,0,0,0,0,-2}, {8,5,0,0,0,0,-2}, {5,3,0,0,0,0,-1}, {3,2,0,0,0,0,-1}, {2,1,0,0,0,0,-1}, {1,1,0,0,0,0,0}, {0,0,0,0,0,0,1} }; struct Matrix { ll a[20][20]; Matrix()//初始化矩阵 { memset(a,0,sizeof(a)); for(int i=0;i<20;i++)a[i][i]=1; } void init() { memcpy(a,b,sizeof(a)); } void show() { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cout<<a[i][j]<<" "; } cout<<endl; } } }; Matrix matrixmul(Matrix a,Matrix b,int grid)// grid*grid 矩阵相乘 { Matrix c; for(int i=0;i<grid;i++) { for(int j=0;j<grid;j++) { c.a[i][j]=0; for(int k=0;k<grid;k++) { c.a[i][j]+=a.a[i][k]*b.a[k][j]; c.a[i][j]%=MOD; } } } return c; } Matrix matrixquickpow(Matrix a,int time)//矩阵a的time次方 { Matrix b; while(time>0) { if(time&1)b=matrixmul(b,a,n); time=time>>1; a=matrixmul(a,a,n); } return b; } int main() { n=7; ll time; while(~scanf("%lld",&time)) { if(time==0){ cout<<7<<endl;continue;} else if(time==1){cout<<11<<endl; continue;} Matrix x; x.init(); int p=(time-2)%6; p=5-p; time=((time-2)/6)+1; x=matrixquickpow(x,time-1); ll ans=0; int temp[8]={197,121,75,46,28,18,1}; for(int i=0;i<8;i++) { ans+=x.a[p][i]*temp[i]; ans=(ans%MOD+MOD)%MOD; } printf("%lld\n",ans%MOD); } }