题目链接：
先用状态压缩求出相邻两层之间的关系，然后用矩阵的快速幂来求
每一层有8个位置然后就有256种状态，但是可以发现，有4个是对称的，也就只用计算70种状态。
我没优化，直接用256种状态进行的计算，如果一直按矩阵的快速幂来求总是栈溢出，必须要先预处理矩阵的1-30次幂的值。
View Code 1 # include2 # include 3 # include 4 # define Mod 1000000007 5 struct matrix{ 6 int s[260][260]; 7 }unit[31]; 8 int n,gg1[260]; 9 bool check(int mm[]) 10 { 11 int i,j; 12 j=0; 13 while(j<=7) 14 { 15 if(mm[j]==1) 16 { 17 if(j+1<=7 && mm[j+1]==1) j++; 18 else break; 19 } 20 j++; 21 } 22 i=1; 23 mm[8]=mm[0]; 24 while(i<=8) 25 { 26 if(mm[i]==1) 27 { 28 if(i+1<=8 && mm[i+1]==1) i++; 29 else break; 30 } 31 i++; 32 } 33 if(j>7 || i>8) return 1; 34 return 0; 35 } 36 int solve() 37 { 38 int i,j,k; 39 __int64 ans; 40 int t[260]; 41 n--; 42 k=0; 43 while(n) 44 { 45 if(n%2) 46 { 47 memset(t,0,sizeof(t)); 48 for(i=0;i<=255;i++) 49 for(j=0;j<=255;j++) 50 { 51 ans=gg1[i]; 52 ans*=unit[k].s[i][j]; 53 ans%=Mod; 54 t[j]+=ans; 55 t[j]%=Mod; 56 } 57 for(i=0;i<=255;i++) 58 gg1[i]=t[i]; 59 } 60 k++; 61 n/=2; 62 } 63 return gg1[255]; 64 } 65 void begin() 66 { 67 int w,i,j,k; 68 __int64 ans; 69 for(w=0;w<30;w++) 70 for(i=0;i<=255;i++) 71 for(j=0;j<=255;j++) 72 { 73 unit[w+1].s[i][j]=0; 74 for(k=0;k<=255;k++) 75 { 76 ans=unit[w].s[i][k]; 77 ans*=unit[w].s[k][j]; 78 ans%=Mod; 79 unit[w+1].s[i][j]+=ans; 80 unit[w+1].s[i][j]%=Mod; 81 } 82 } 83 } 84 int main() 85 { 86 int i,j,k,t,ncase; 87 int ans; 88 int a[10],mm[10],gg[260]; 89 a[0]=1; 90 for(i=1;i<=8;i++) 91 a[i]=a[i-1]*2; 92 93 94 for(i=0;i<=254;i++) 95 { 96 for(j=0;j<=7;j++) 97 { 98 if((i&a[j])!=0) mm[j]=1; 99 else mm[j]=0;100 }101 if(check(mm)) gg[i]=1;102 else gg[i]=0;103 }104 gg[255]=2;105 106 for(i=0;i<=255;i++)107 {108 for(k=0;k<=255;k++)109 {110 unit[0].s[i][k]=0;111 ans=k;112 for(j=0;j<=7;j++)113 { 114 if((i&a[j])==0)115 {116 if((k&a[j])==0) break;117 mm[j]=0;ans-=a[j];118 }119 }120 if(j<=7) continue;121 if(gg[ans]==0) continue;122 unit[0].s[i][k]=1;123 }124 }125 unit[0].s[255][255]=2;126 begin();127 scanf("%d",&ncase);128 for(t=1;t<=ncase;t++)129 {130 scanf("%d",&n);131 for(i=0;i<=255;i++)132 gg1[i]=gg[i];133 ans=solve();134 printf("Case %d: %d\n",t,ans);135 }136 return 0;137 }