题目链接：https://nanti.jisuanke.com/t/31721
题意：有鱼，肉，巧克力三种食物，有N个小时，现在要求每小时吃一种食物，而且下边的吃法不合法：
- 续三小时吃一种食物
- 连续三小时三种食物都吃并且中间吃的巧克力
- 连续三小时，两边吃巧克力，中间吃了鱼或者肉
问N小时内共有几种吃法。
解析：假设鱼，巧克力，肉分别用字符X，Y，Z表示，那么合法的长度为N的字符串的组成方案数即是答案。
考虑由前面时间的状态推出后面时间的状态，但是当加一个新字符时，我们要考虑旧字符串最后两个字符的状态，这样是不好推的。我们可以考虑每次添加两个新字符（共9种），然后用旧字符串最后两个字符（共9种）的状态进行转移。生成一个如下9*9的矩阵。
其中1代表两个字符串能连接，0表示不能，比如左边列"ZY"与上面行"ZX"，表示""ZY"之后加上"ZX"其值为1表示可以加。
那么这个初始矩阵中1的个数就表示所有长度为4的合法字符串的方案数，那么对于两个这种矩阵相乘就表示在原来长度为4的字符串上再加2个字符，矩阵中所有元素和就是长度为6的合法字符串的方案数。
那么对于N为偶数直接对初始矩阵求(N-2)/2次幂，然后最终矩阵中元素的和就是方案总数。N为奇数时，那么N-1为偶数，先生成长度为N-1对应的矩阵（初始矩阵求(N-2-1)/2次幂）,然后在乘以下矩阵，表示加一个字符，最终矩阵的元素和就是总方案数：
此矩阵与上面矩阵原理相同。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll M=9;ll N;struct Matrix
{Matrix(){memset(a,0,sizeof(a));}ll a[M][M];void init(){for(ll i=0;i<M;i++)for(ll j=0;j<M;j++)a[i][j]=0;for(ll i=0;i<M;i++)a[i][i]=1;}
}A,B,C;
Matrix mul(Matrix a,Matrix b) //(a*b)%mod
{Matrix ans;ll i,j,k;for(i=0;i<M;i++)for(j=0;j<M;j++){for(k=0;k<M;k++)ans.a[i][j]+=a.a[i][k]*b.a[k][j];ans.a[i][j]%=mod;}return ans;
}
Matrix pow(Matrix a,ll n) //(a^n)%mod
{Matrix ans;ans.init();while(n){if(n&1)ans=mul(ans,a);n>>=1;a=mul(a,a);}return ans;
}
ll sum(Matrix a,int col)
{ll res=0;for(int i=0;i<9;i++)for(int j=0;j<col;j++)res=(res+a.a[i][j])%mod;return res;
}int main()
{A.a[0][0]=0; A.a[0][1]=0; A.a[0][2]=0; A.a[0][3]=1; A.a[0][4]=1; A.a[0][5]=0; A.a[0][6]=1; A.a[0][7]=1; A.a[0][8]=1;A.a[1][0]=1; A.a[1][1]=0; A.a[1][2]=1; A.a[1][3]=1; A.a[1][4]=0; A.a[1][5]=1; A.a[1][6]=0; A.a[1][7]=0; A.a[1][8]=0;A.a[2][0]=1; A.a[2][1]=1; A.a[2][2]=1; A.a[2][3]=1; A.a[2][4]=1; A.a[2][5]=0; A.a[2][6]=1; A.a[2][7]=1; A.a[2][8]=0;A.a[3][0]=0; A.a[3][1]=1; A.a[3][2]=1; A.a[3][3]=0; A.a[3][4]=0; A.a[3][5]=0; A.a[3][6]=1; A.a[3][7]=1; A.a[3][8]=1;A.a[4][0]=1; A.a[4][1]=0; A.a[4][2]=1; A.a[4][3]=0; A.a[4][4]=0; A.a[4][5]=0; A.a[4][6]=1; A.a[4][7]=0; A.a[4][8]=1;A.a[5][0]=1; A.a[5][1]=1; A.a[5][2]=1; A.a[5][3]=0; A.a[5][4]=0; A.a[5][5]=0; A.a[5][6]=1; A.a[5][7]=1; A.a[5][8]=0;A.a[6][0]=0; A.a[6][1]=1; A.a[6][2]=1; A.a[6][3]=0; A.a[6][4]=1; A.a[6][5]=1; A.a[6][6]=1; A.a[6][7]=1; A.a[6][8]=1;A.a[7][0]=0; A.a[7][1]=0; A.a[7][2]=0; A.a[7][3]=1; A.a[7][4]=0; A.a[7][5]=1; A.a[7][6]=1; A.a[7][7]=0; A.a[7][8]=1;A.a[8][0]=1; A.a[8][1]=1; A.a[8][2]=1; A.a[8][3]=0; A.a[8][4]=1; A.a[8][5]=1; A.a[8][6]=0; A.a[8][7]=0; A.a[8][8]=0;C.a[0][0]=0; C.a[0][1]=1; C.a[0][2]=1;C.a[1][0]=1; C.a[1][1]=1; C.a[1][2]=0;C.a[2][0]=1; C.a[2][1]=1; C.a[2][2]=1;C.a[3][0]=1; C.a[3][1]=0; C.a[3][2]=1;C.a[4][0]=1; C.a[4][1]=0; C.a[4][2]=1;C.a[5][0]=1; C.a[5][1]=0; C.a[5][2]=1;C.a[6][0]=1; C.a[6][1]=1; C.a[6][2]=1;C.a[7][0]=0; C.a[7][1]=1; C.a[7][2]=1;C.a[8][0]=1; C.a[8][1]=1; C.a[8][2]=0;int T;scanf("%d",&T);while(T--){scanf("%lld",&N);if(N==1){printf("3\n");}else if(N==2){printf("9\n");}else if(N==3){printf("20\n");}else if((N&1)==0){B=pow(A,(N-2)/2);printf("%lld\n",sum(B,9));}else{B=pow(A,(N-2-1)/2);Matrix D;for(int i=0;i<9;i++){for(int j=0;j<3;j++){for(int k=0;k<9;k++)D.a[i][j]+=B.a[i][k]*C.a[k][j];D.a[i][j]%=mod;}}printf("%lld\n",sum(D,3));}}return 0;
}/*
1 3
2 9
3 20
4 46
5 106
6 244
7 560
8 1286
9 2956
10 6794
11 15610
12 35866
13 82416
14 189384
15 435170
16 999936
*/