题意：个n个方块涂色， 只能涂红黄蓝绿四种颜色，求最终红色和绿色都为偶数的方案数。
该题我们可以想到一个递推式 。 设a[i]表示到第i个方块为止红绿是偶数的方案数， b[i]为红绿恰有一个是偶数的方案数， c[i]表示红绿都是奇数的方案数。
那么有如下递推可能：
递推a[i+1]：1.到第i个为止都是偶数，且第i+1个染成蓝或黄；2.到第i个为止红绿恰有一个是奇数，并且第i+1个方块染成了奇数对应的颜色。
递推b[i+1]：1.到第i个为止都是偶数，且第i+1个染成红或绿；2.到第i个为止红绿恰有一个是奇数，并且第i+1个方块染成了蓝或黄；3.到第i个方块为止红火绿都是奇数，并且第i+1个染成红火绿。
递推c[i+1]：1.到第i个为止红绿恰有一个是奇数， 并且第i+1个方块染成偶数对应的颜色；2.到第i个为止红绿都是奇数，并且第i+1个方块染成蓝或黄。
即a[i+1] = 2*a[i] + b[i];
b[i+1] = 2*a[i] + 2*b[i] + 2*c[i];
c[i+1] = b[i] + 2*c[i];
因为DP的过程中，每一步都是在重复上一个过程， 所以可以用矩阵相乘来优化算法。
将上述递推式写成矩阵相乘的形式：
{ a[i] } {2 1 0}^i{a[0] }
{ b[i] } = {2 2 2} {b[0] }
{ c[i] } {0 1 2} {c[0] }
然后用矩阵快速幂就可以了。
AC代码
#include<stdio.h>
#include<string.h>
#define mod 10007
struct Mat
{
long long mat[][];
}; Mat operator * (Mat a,Mat b)
{
int n=;
Mat c;
c.mat[][]=c.mat[][]=c.mat[][]=c.mat[][]=c.mat[][]=c.mat[][]=c.mat[][]=c.mat[][]=c.mat[][]=;
int i,j,k;
for(k = ; k < n ; k++)
{
for(i = ; i < n ;i++)
{
if(a.mat[i][k]==) continue;//优化
for(j = ;j < n ;j++)
{
if(b.mat[k][j]==) continue;//优化
c.mat[i][j] = (c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;
}
}
}
return c;
}
Mat operator ^(Mat a,int k)
{
int n=;
Mat c;
int i,j;
for(i = ; i < n ;i++)
for(j = ; j < n ;j++)
c.mat[i][j] = (i==j);
for(; k ;k >>= )
{
if(k&) c = c*a;
a = a*a;
}
return c;
}
int main( )
{
long long n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
Mat A;
A.mat[][]=;A.mat[][]=;A.mat[][]=;
A.mat[][]=;A.mat[][]=;A.mat[][]=;
A.mat[][]=;A.mat[][]=;A.mat[][]=;
Mat ans=A^n;
printf("%lld\n",ans.mat[][]);
}
return ;
}