题目链接：
POJ 3734 Blocks
题意：
有n个格子，每个格子可以涂 red,blue,green,yellow 四种颜色之一，但是需要保证所有的red和green格子数均为偶数，问一共有多少种涂色方案？
如： n=2时:RR,GG,BY,YB,BB,YY,共6种。数据范围1<=n<=(1e9)
分析：
用 dp[i][j][k] 表示前i个格子的涂色方案，其中j=0/k=0表示red/green格子数是奇数，j=1/k=1表示red/green格子数是偶数，
初始化：
dp[1][0][0]=0,dp[1][0][1]=dp[1][1][0]=1,dp[1][1][1]=2；状态转移方程：
dp[i][0][0]=2*dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][1][0];
dp[i][0][1]=dp[i-1][0][0]+2*dp[i-1][0][1]+dp[i-1][1][1];
dp[i][1][0]=dp[i-1][0][0]+2*dp[i-1][1][0]+dp[i-1][1][1];
dp[i][1][1]=dp[i-1][0][1]+dp[i-1][1][0]+2*dp[i-1][1][1];但是由于n的范围是1<=n<=(1e9)，如果用递推的话数组存不下啊。。。
所以可以用矩阵快速幂解决。
定义中间矩阵为：
| 2 1 1 0 |
| 1 2 0 1 |
| 1 0 2 1 |
| 0 1 1 2 |初始化的矩阵为：
| 0 |<-- dp[0][0][0]
| 1 |<-- dp[0][0][1]
| 1 |<-- dp[0][1][0]
| 2 |<-- dp[0][1][1]将中间矩阵求(n-1)次幂，然后乘以初始化的矩阵就能得到答案了。
//396K 16MS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const long long mod=10007;int T,n;struct Matrix{int row,col;long long data[10][10];
};inline Matrix mul(Matrix a,Matrix b)
{Matrix ans;ans.row=a.row,ans.col=b.col;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++){for(int j=1;j<=ans.col;j++){for(int k=1;k<=a.col;k++){ans.data[i][j]+=a.data[i][k]*b.data[k][j]%mod;ans.data[i][j]=(ans.data[i][j]+mod)%mod;}}}return ans;
}inline Matrix quick_power(Matrix a,int m)
{Matrix ans,tmp=a;ans.row=ans.col=a.row;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++) { ans.data[i][i]=1; }while(m){if(m&1) ans=mul(ans,tmp);tmp=mul(tmp,tmp);m>>=1;}return ans;
}int main()
{//freopen("poj3734in.txt","r",stdin);scanf("%d",&T);while(T--){
scanf("%d",&n);Matrix ans,tmp;ans.row=ans.col=tmp.row=4,tmp.col=1;ans.data[1][1]=ans.data[2][2]=ans.data[3][3]=ans.data[4][4]=2;ans.data[1][2]=ans.data[1][3]=ans.data[2][1]=ans.data[2][4]=1;ans.data[3][1]=ans.data[3][4]=ans.data[4][2]=ans.data[4][3]=1;ans.data[1][4]=ans.data[2][3]=ans.data[3][2]=ans.data[4][1]=0;tmp.data[1][1]=0,tmp.data[4][1]=2;tmp.data[2][1]=tmp.data[3][1]=1;ans=quick_power(ans,n-1);tmp=mul(ans,tmp);printf("%lld\n",(tmp.data[4][1]+mod)%mod);}return 0;
}