自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:09:17，当前版本为作者最后更新于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;

}