【BZOJ5505】[GXOI/GZOI2019]逼死强迫症（矩阵快速幂）
题面
题解
如果没有那两个\(1*1\)的东西，答案就是斐波那契数，可以简单的用\(dp\)得到。
大概是设\(f[i]\)表示当前除了到第\(i\)列的方案数，转移是考虑用\(2*1\)竖着覆盖一列还是\(2\)个\(1*2\)横着覆盖两列，得到转移\(f[i]=f[i-1]+f[i-2]\)。
现在回假设要在这一行放上第二个\(1*1\)，那么直到前一个\(1*1\)所在列之前的所有方块都被唯一确定了，而左侧就是随便放的方案数，即斐波那契数列。
设\(g[i]\)表示上面的\(f[i]\)，\(f[i]\)为答案，\(s[i]\)为\(g[i]\)前缀和。
那么\(f[i]=f[i-1]+f[i-2]+2h[i-3]\)，即考虑当前在哪一行放上这个\(1*1\)的东西，有两种方案数，接下来可以在任何一个地方把这个东西补齐，而前面可以任意摆放。
根据斐波那契数列的性质，\(h[i-3]=g[i-1]-1\)，所以拿矩阵快速幂维护一下斐波那契数列和\(dp\)数列就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 1000000007
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
const int N=5;
struct Matrix
{
int s[N][N];
void clear(){memset(s,0,sizeof(s));}
void init(){clear();for(int i=0;i<N;++i)s[i][i]=1;}
int*operator[](int x){return s[x];}
}A[32],B,P,Ans;
Matrix operator*(Matrix a,Matrix b)
{
Matrix c;c.clear();
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
for(int k=0;k<N;++k)
c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%MOD;
return c;
}
Matrix fpow(int b)
{
Matrix s;s.init();
for(int i=0;b;++i,b>>=1)
if(b&1)s=s*A[i];
return s;
}
int main()
{
B[0][2]=B[0][3]=B[0][4]=1;
P[0][1]=P[1][0]=P[1][1]=P[2][3]=P[3][2]=P[3][3]=P[4][4]=1;
P[2][1]=P[3][1]=2;P[4][1]=MOD-2;
A[0]=P;for(int i=1;i<32;++i)A[i]=A[i-1]*A[i-1];
int T=read();
while(T--)
{
int n=read();
if(n==1){puts("0");continue;}
if(n==2){puts("0");continue;}
Ans=B*fpow(n-2);
printf("%d\n",Ans[0][1]);
}
return 0;
}