题意：
有长度为n的一排格子，每个格子里面可以任意填入1,2,3,4四个数字，问1,2都为偶数个的方案
T组数据，每组数据一个n(<=1e9)
样例输入
2
1
2
样例输出
2
6
分析
设dp[i][0/1/2/3]分别为处理到第i个，1和2的个数分别为 全偶、1偶2奇、1奇2偶，全奇
那么dp转移方程为
dp[i][0]=2dp[i-1][0]+dp[i-1][1]+dp[i-1][2] 填的分别是 3/4 1 2
dp[i][1]=dp[i-1][0]+2dp[i-1][1]+dp[i-1][3] 填的分别是 2 3/4 1
dp[i][2]=dp[i-1][0]+2dp[i-1][2]+dp[i-1][3] 填的分别是 1 3/4 2
dp[i][3]=dp[i-1][1]+dp[i-1][2]+2dp[i-1][3] 填的分别是 1 2 3/4
我们发现dp[i][1]和dp[i][2]可以合并在一起
那么将dp[i][1]和dp[i][2]合并为dp[i][1]，dp[i][3]改为dp[i][2]
那么dp转移方程简化为：(简化方式为上面2式和3式相加，dp[i][1]和dp[i][2]替换为dp[i][1]，dp[i][3]替换为dp[i][2])
dp[i][0]=2dp[i-1][0]+dp[i-1][1]
dp[i][1]=2dp[i-1][0]+2dp[i-1][1]+2dp[i-1][3]
dp[i][2]=dp[i-1][1]+2dp[i-1][2]
我们发现n=1e9直接推会T，所以就上矩阵快速幂，初始矩阵为
| 2 2 0 |
| 0 0 0 |
| 0 0 0 |
转置矩阵为
| 2 2 0 |
| 1 2 1 |
| 0 2 2 |
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll long long
#define inf (1<<29)
using namespace std;
ll T,n;
const ll mo=;
inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} struct Mat{
ll a[][];
Mat(){memset(a,,sizeof(a));}
inline ll * operator [] (const int x){return a[x];}
inline Mat operator *(Mat b)
{
Mat ans;
rep(i,,) rep(j,,) rep(k,,)
(ans[i][j]+=(a[i][k]*b[k][j]))%=mo;
return ans;
}
}; void work()
{
Mat S,T;
S[][]=,S[][]=,S[][]=,
T[][]=,T[][]=,
T[][]=,T[][]=,T[][]=,
T[][]=,T[][]=;
while(n)
{
if(n&)S=S*T;
T=T*T;
n>>=;
}
printf("%lld\n",S[][]);
} int main()
{
T=read();
while(T--)
{
n=read();
work();
}
return ;
}