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

· · 题解

大佬们的做法都太神啦，我这个菜鸡只会暴力 dp。

首先我们发现题目这个东西不好设状态，所以我们先做一个简单的容斥，将所有方案数量减去不合法（即两块单砖挨在一起了）的数量。

不合法的数量是多少呢？我们发现两块砖既然挨在一起了，就可以直接看作是一块大的砖，所以就是斐波那契数列。但是这里由于每一块大砖都可以变成两块小砖，所以实际上要乘上 n。

对于所有方案的我们暴力 dp。设 f_{i,j,k} 为当前考虑到第 i 行，该行已经被放置了 k 块，还有 j 块小砖没有用的方案数，则不难写出状态转移。然后我们发现 j 和 k 的取值是 0 到 2，我们将其合为一维，这样就可以直接上矩乘了。

这个算法的时间复杂度是 O(9^3\log n)。还是那句话，因为 9 是常数，所以实际上是 O(\log n)。

下面是奇丑无比的代码，使用了 C++11 的写法减少码量，在提交后成功拿到全谷最劣解。

#include<vector>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
typedef long long ll;
const ll mod=1e9+7;
typedef vector<ll> col;
typedef vector<col> matrix;
matrix operator *(matrix a,matrix b){
    int n=a.size();
    matrix c;
    for(int i=0;i<n;i++){
        c.push_back(col());
        for(int j=0;j<n;j++) c[i].push_back(0);
    }
    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]+a[i][k]*b[k][j]%mod)%mod;
    return c;
}
matrix ksm(matrix a,ll b){
    matrix ans;
    int n=a.size();
    for(int i=0;i<n;i++){
        ans.push_back(col());
        for(int j=0;j<n;j++) ans[i].push_back(0);
    }
    for(int i=0;i<n;i++) ans[i][i]=1;
    while(b>0){
        if(b%2==1) ans=ans*a;
        a=a*a;
        b/=2;
    }
    return ans;
}
const matrix m1={{0,1},{1,1}},
             m2={
                    {1,0,1,0,0,0,0,0,0},
                    {0,1,0,0,0,0,0,0,0},
                    {1,0,0,0,0,0,0,0,0},
                    {0,2,0,1,0,1,0,0,0},
                    {1,0,0,0,1,0,0,0,0},
                    {0,0,0,1,0,0,0,0,0},
                    {1,0,0,0,2,0,1,0,1},
                    {0,0,0,1,0,0,0,1,0},
                    {0,0,0,0,0,0,1,0,0}
                };
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif  
    int t=readint();
    while(t--){
        int n=readint();
        ll ans=ksm(m2,n)[6][0];
        matrix res=ksm(m1,n);
        ans=(ans+mod-(res[0][0]+res[0][1])%mod*n%mod)%mod;
        printf("%d\n",(int)ans);
    }
    return 0;
}

这个算法其实是有优化的余地的，比如 j=0,k=1 的状态就完全没有必要保留。但是我懒，所以就不写了。