题目大意
有n个方块，有1,2,3,4四种颜色对其进行染色，求1,2颜色的方块个数均为偶数的方案数对10007取模的值。
分析
我们假设1表示这个颜色个数是奇数，0表示是偶数，所以对于所有状态我们可以分为四种，每种对应一个二元组 ，二元组的第一项表示颜色1，第二项表示颜色2，这四种分别是(1,1)，(1,0)，(0,1)，(0,0)。但是我们不难发现(1,0)和(0,1)这两种状态可以合为一种，所以我们可以推出：
(1,1) = 2*(1,1) + (1,0)
(1,0) = (1,1) + 2*(1,0) + 2*(0,0)
(0,0) = 2*(0,0) + (1,0)
我们通过这个便可以得到转移矩阵了。详见代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int mod = ;
struct mat {
int g[][];
};
inline mat operator * (mat a,mat b){
mat c;
for(int i=;i<=;i++)
for(int j=;j<=;j++){
int x=;
for(int k=;k<=;k++)
x=(x+a.g[i][k]*b.g[k][j]%mod)%mod;
c.g[i][j]=x;
}
return c;
}
inline int pw(int p){
mat res,a;
a.g[][]=a.g[][]=a.g[][]=a.g[][]=a.g[][]=;
a.g[][]=a.g[][]=;
a.g[][]=a.g[][]=;
res=a;
while(p){
if(p&)res=res*a;
a=a*a;
p>>=;
}
return res.g[][];
}
int main(){
int n,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",pw(n-));
}
return ;
}