题解 P5303 【[GXOI/GZOI2019]逼死强迫症】

mrsrz · 2019-04-17 12:32:01 · 题解

令f_i表示N=i时的方案数。

考虑最右侧多出了一列，我们可以直接放一个1\times 2的方块，也可以横着放两个1\times 2的方块覆盖2\times 2的区域。

这是最右边不放1\times 1的方块的情况。

考虑最右侧放了1\times 1的方块。

发现另一个这个方块能放在1\sim i-2列上，且每列恰只有一个位置可行（同行还是异行与列数差的奇偶性有关）。

然后这个1\times 1的方块左边的区域可以任意摆放，右边的区域只有一种方案。

设g_i表示2\times i的区域只用1\times 2的方块覆盖的方案数，h_i表示g_i的前缀和（特别地，g_0=1\）。

那么有f_i=f_{i-1}+f_{i-2}+2h_{i-3}。

发现g是斐波那契数列，而斐波那契数列的前缀和满足h_i=g_{i+2}-1。

所以f_i=f_{i-1}+f_{i-2}+2g_{i-1}-2。

用矩阵快速幂维护即可。需要维护5\times 5的矩阵。

时间复杂度O(125T\log n)。

Code：

#include<cstdio>
#include<cstring>
const int md=1e9+7;
typedef long long LL;
struct mat{
    int a[5][5];
    inline mat(){memset(a,0,sizeof a);}
    inline mat operator*(const mat&b)const{
        mat c;
        for(int i=0;i<5;++i)
            for(int k=0;k<5;++k)
                for(int j=0;j<5;++j)
                    c.a[i][j]=(c.a[i][j]+(LL)a[i][k]*b.a[k][j])%md;
        return c;
    }
}s;
mat pow(mat a,int b){
    mat ret;
    ret.a[0][0]=ret.a[1][1]=ret.a[2][2]=ret.a[3][3]=ret.a[4][4]=1;
    for(;b;b>>=1,a=a*a)
        if(b&1)ret=ret*a;
    return ret;
}
int main(){
    s.a[0][1]=s.a[1][0]=s.a[1][1]=s.a[2][3]=s.a[3][2]=s.a[3][3]=s.a[4][4]=1;
    s.a[3][1]=2,s.a[4][1]=md-1;
    int T;
    for(scanf("%d",&T);T--;){
        int n;
        scanf("%d",&n);
        if(n<3)
            puts("0");
        else{
            mat ans;
            ans.a[0][2]=1,ans.a[0][3]=ans.a[0][4]=2;
            printf("%d\n",(ans*pow(s,n-2)).a[0][1]);
        }
    }
    return 0;

}