我们设 Bn 代表从某个角出发，然后走遍所有格子回到同一列的方案数目。
Bn=2×Bn−1=2n−1
同样，我们设 An 代表从某个角出发，然后走遍所有格子的方案数。
则 An=Bn+2×An−1+4×An−2
其中 Bn 代表回到了当前列的方案数， An−1 代表先填满当前列然后走到相邻的列处理同样的一个子问题，
An−2 代表通过对角线方式先走完当前列与相邻列的格子，然后剩下的 n−2 列即相同子问题。
因为有四个角，所以我们的结果要乘以 4 ，即 4×An 。
当然，真实情况下我们不一定是从四个角出发的，还有另一种情况就是中间的列
考虑中间的第 i 列
我们可以先从第 i 列往左走完所有的格子回来，然后再往右走完所有的格子；
也可以先往右走完所有的格子回来，再往左走完所有的格子。
于是总的方案数即 2×(4×Bi−1×An−i+4×Bn−i×Ai−1) ，其中 2 代表第 i 列有两个格子可选为初始点， 4 代表分别向左右两边行走时的选择方案数 2×2 。
#include<cstdio> #define ll long long const int N=10010,P=1000000007; ll a[N],b[N],n; int T; int main() { register int i,j; b[1]=1; for (i=2;i<=N;i++) b[i]=(b[i-1]*2)%P; a[1]=1;a[2]=6; for (i=3;i<=N;i++) a[i]=(2*a[i-1]+b[i]+4*a[i-2])%P; scanf("%d",&T); for (j=1;j<=T;j++) { int n;scanf("%d",&n);ll ans=0; for (i=2;i<=n-1;i++) ans=(ans+16*b[i-1]%P*a[n-i])%P; ans=(ans+4*a[n])%P; if (n==1) ans=2; printf("%lld\n",ans); } return 0; }
