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

· · 题解

可以先去考虑没有1 \times 1的砖块的情况，对于最后一个位置只有两种情况，一个是竖着用一块砖铺设2 \times 1，另一个为横着用两块砖铺设2 \times 2。

设没有1 \times 1的砖块的情况铺2 \times n的路的方案数为F_n，根据上面的分析得F_n=F_{n-1}+F_{n-2}，发现其为斐波那契数列。

用同样的方法考虑有1 \times 1的砖块的情况，设f_n表示按题意铺2 \times n的路的方案数，当最后的位置没有1 \times 1的砖块的影响时，其也是有两种放置情况，也就是说f_{i-1}和f_{i-2}对f_i都有贡献。

当最后一个位置需要铺设为1 \times 1的砖块时，可以发现该砖块到另一个砖块的区间的铺设情况是唯一的，所以这种情况决定方案数的是这两个1 \times 1的砖块形成的区间之前的2 \times 1砖块铺设情况。因此我们得：

f_i=f_{i-1}+f_{i-2}+2\sum_{j=0}^{i-3}F_j

设S_i=\sum\limits_ {j=0}^{i}F_j，得f_i=f_{i-1}+f_{i-2}+2S_{i-3}

然后就可以递推来求解了，但是发现n很大，所以用矩阵快速幂来加速递推。

设矩阵\begin{bmatrix} f_i&f_{i-1}&F_{i-2}&F_{i-3}&S_{i-3}\end{bmatrix} \quad，经过分析得，将其转移到\begin{bmatrix} f_{i+1}&f_i&F_{i-1}&F_{i-2}&S_{i-2}\end{bmatrix} \quad的转移矩阵为：

\begin{bmatrix} 1&1&0&0&0\\ 1&0&0&0&0\\ 2&0&1&1&1\\ 0&0&1&0&0\\ 2&0&0&0&1\\ \end{bmatrix} \quad

然后每次询问矩阵快速幂一下就好了。

code: 
#include<bits/stdc++.h>
#define p 1000000007
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
ll T,n;
struct matrix
{
    ll a[6][6];
    matrix()
    {
        memset(a,0,sizeof(a));
    }
}m,ans;
matrix operator *(const matrix &a,const matrix &b)
{
    matrix c;
    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]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%p+p)%p;
    return c;
}
matrix qp(matrix x,ll y)
{
    matrix e;
    for(int i=0;i<5;++i) e.a[i][i]=1;
    while(y)
    {
        if(y&1) e=e*x;
        x=x*x,y>>=1;
    }
    return e;
}
ll m1[6][6]=
{
    {2,0,1,1,1}
};
ll m2[6][6]=
{
    {1,1,0,0,0},
    {1,0,0,0,0},
    {2,0,1,1,1},
    {0,0,1,0,0},
    {2,0,0,0,1}
};
int main()
{
    read(T);
    memcpy(ans.a,m1,sizeof(ans.a));
    memcpy(m.a,m2,sizeof(m.a));
    while(T--)
    {
        read(n);
        if(n<3) puts("0");
        else printf("%lld\n",(ans*qp(m,n-3)).a[0][0]);
    }
    return 0;
}