题目
题解
先考虑没有$1\times 1$块的方案数
对于第$i$列，要么是从第$i-1$列加上一块$2\times 1$的块转移过来的，要么是从第$i-2$列加上两块$1\times 2$的块转移过来的，所以前$i$列的方案数为$f_i=f_{i-1}+f_{i-2}$，即斐波那契数列当然这并不重要
现在考虑加上$1\times 1$块的情况，设$g_i$表示第$i$列和之前列中已经把两个$1\times 1$的块放完了的方案数，分第$i$列是否放第二个块讨论
- 不放，那么就是上面没有$1\times 1$块的转移，要么从第$i-1$列转移要么从第$i-2$列转移，$g_i=g_{i-1}+g_{i-2}$
- 放，那么第$1$块可以放在$1\sim i-2$的任意一列（假设为$j$），但是每一列只对应一种放法，且$j\sim i-1$中间这些列也只有一种放法，而$j$前面的列可以随便放，也就是没有$1\times 1$块的情况，所以$g_i=2\sum_{j=1}^{i-3}f_j=2(f_{i-1}-1)$
所以总的方案数为$g_i=g_{i-1}+g_{i-2}+2f_{i-1}-2$，用矩阵快速幂优化即可
代码
// luogu-judger-enable-o2
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int N=5,mod=1e9+7;
struct Mx{
int a[N][N];
}a,emp,A,B;
int n,T;
Mx operator* (Mx a,Mx b)
{
Mx c=emp;
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
for(int k=0;k<5;++k)
(c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod)%=mod;
return c;
}
Mx Pow(Mx a,int b)
{
Mx ans=emp;
for(int i=0;i<5;++i)
ans.a[i][i]=1;
for(;b;b>>=1,a=a*a)
if(b&1) ans=ans*a;
return ans;
}
int main()
{
scanf("%d",&T);
a.a[0][0]=a.a[0][1]=a.a[0][4]=a.a[3][2]=a.a[4][4]=a.a[1][0]=a.a[2][2]=a.a[2][3]=1,a.a[0][2]=a.a[0][3]=2;
while(T--)
{
scanf("%d",&n);
if(n==1||n==2) {puts("0");continue;}
A=a,B=emp,B.a[0][0]=B.a[2][0]=2,B.a[3][0]=1,B.a[4][0]=mod-2,A=Pow(A,n-3),printf("%d\n",(A*B).a[0][0]);
}
return 0;
}
