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

· · 题解

推式子题。

首先，我们考虑算出不包含 1\times 1 的块的答案。

因为每个 1\times 2 的块要么横着放，要么两个一起竖着放，因此存在关系式 F_n=F_{n-1}+F_{n-2} ，就是斐波那契数列。

然后考虑包含 1\times 1 的块的答案。

可以发现，这两个块放完后，中间的块就最多只有 1 种放法。而这两个块的整体最小是 2\times 3 的块。再算上两个块上下摆放，两个块构成 2\times n(n\ge 3) 大小的方案数都是 2 。因此我们就得到了一个式子:

ans=2\sum_{i=3}^n\sum_{j=0}^{n-i} F_j*F_{n-i-j}

推一下:

ans=2\sum_{i=3}^n\sum_{j=0}^{n-i} F_j*F_{n-i-j} =2\sum_{i=0}^{n-3} F_i\sum_{j=0}^{n-3-i} F_j =2\sum_{i=0}^{n-3}F_i*(F_{n-1-i}-1) =2-2F_{n-1}+2\sum_{i=0}^{n-3}F_i*F_{n-1-i}

我们设 S_n=\sum_{i=0}^n F_i*F_{n-i} ，则:

答案就是 2-2F_{n-1}+2(S_{n-1}-F_{n-2}*F_1-F_{n-1}*F_{0}) ，即 2(1+S_{n-1}-2F_{n-1}-F_{n-2}) 。

S_n=\sum_{i=0}^n F_i*F_{n-i} =F_n+F_{n-1}+\sum_{i=0}^{n-2} F_i*(F_{n-i-1}+F_{n-i-2}) =F_n+F_{n-1}+\sum_{i=0}^{n-2}F_i*F_{n-1-i}+\sum_{i=0}^{n-2} F_i*F_{n-2-i} =F_n+\sum_{i=0}^{n-1}F_i*F_{n-1-i}+\sum_{i=0}^{n-2} F_i*F_{n-2-i} =F_n+S_{n-1}+S_{n-2}

考虑利用矩阵快速幂解决这个问题。可以列出转移矩阵:

\begin{bmatrix}F_{n-2}\\F_{n-1}\\S_{n-2}\\S_{n-1}\end{bmatrix}\begin{bmatrix}0&1&0&0\\1&1&0&0\\0&0&0&1\\1&1&1&1\end{bmatrix}=\begin{bmatrix}F_{n-1}\\F_n\\S_{n-1}\\S_n\end{bmatrix}

如果预处理出 2^k 的矩阵，总复杂度为 O(64\log W+\sum 16\log n) 。

代码:

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<queue>
#include<iostream>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;

    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
        x*=f;
    }

    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static uint32 sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
    }
}
using namespace IO;

void file()
{
#ifndef ONLINE_JUDGE
    FILE*DSD=freopen("water.in","r",stdin);
    FILE*CSC=freopen("water.out","w",stdout);
#endif
}

const int mod=1e9+7;

static struct matrix
{
    int c[4][4];

    matrix operator*(const matrix&a)const
    {
        matrix x;
        Rep(i,0,3)Rep(j,0,3)
            x.c[i][j]=((ll)c[i][0]*a.c[0][j]+(ll)c[i][1]*a.c[1][j]+
                (ll)c[i][2]*a.c[2][j]+(ll)c[i][3]*a.c[3][j])%mod;
        return x;
    }
}bs[35];

static int n;

inline void init(){read(n);}

static int vec[4],as[4];

inline void solve()
{
    if(n<=3){write(n==3?2:0);return;}
    n-=2;
    vec[0]=vec[1]=vec[2]=1,vec[3]=2;
    Rep(i,0,30)if(n>>i&1)
    {
        Rep(j,0,3)
        as[j]=((ll)vec[0]*bs[i].c[j][0]+(ll)vec[1]*bs[i].c[j][1]
        +(ll)vec[2]*bs[i].c[j][2]+(ll)vec[3]*bs[i].c[j][3])%mod;
        Rep(j,0,3)vec[j]=as[j];
    }
    write((((vec[3]-vec[0]-2ll*vec[1]+mod+mod+mod)%mod<<1)%mod+2)%mod);
}

int main()
{
    file();
    bs[0].c[0][1]=bs[0].c[1][0]=bs[0].c[1][1]=bs[0].c[2][3]=bs[0].c[3][0]=bs[0].c[3][1]=bs[0].c[3][2]=bs[0].c[3][3]=1;
    Rep(i,1,30)bs[i]=bs[i-1]*bs[i-1];
    static int _;
    read(_);
    while(_--)init(),solve();
    flush();
    return 0;
}