题解：LGOJT8634 [蓝桥杯 2015 国 A] 铺瓷砖

Edward1002001 · 2023-12-22 11:13:11 · 题解

题意：在一个 n \times m 的（无障碍）网格中铺“二折”和“三凸”方块，求方案数。

一个显然的想法是，记前两行的瓷砖有无状态，在铺放瓷砖的某个固定位置检测瓷砖所应该占有的地方有无方块，并将其使用矩阵转移，这样的做法是 O(m4^m+64^m\log n) 的，显然过不去，下面是这种做法的简要图示和代码，图中，红色表示不能有值，绿色表示需要有值，数字标号按代码中顺序排列，灰色表示轮廓线。

#include<cstdio>
#include<cstring>
typedef long long ll;
typedef unsigned uint;
const uint mod=65521;
template<int n>struct mtrx{uint a[n][n];};
template<int n>
mtrx<n> mul(mtrx<n> x,mtrx<n> y)
{
    mtrx<n> res{0};
    for(int i=0;i<n;++i)
        for(int k=0;k<n;++k)if(x.a[i][k])
        {
            uint val=x.a[i][k],*x1=res.a[i],*x2=y.a[k];
            for(int j=0;j<n;++j)x1[j]=(x1[j]+x2[j]*val)%mod;
        }
    return res;
}
const int msk[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
const int zsk[13]={~1,~2,~4,~8,~16,~32,~64,~128,~256,~512,~1024,~2048,~4096};
mtrx<4096> xres,res,T[6];
void pre(int m)
{
    memset(&xres,0,sizeof xres);memset(&res,0,sizeof res);
    for(int i=0;i<msk[m+m];++i)xres.a[i][i]=1;
    for(int i=0;i<m;++i)
    {
        mtrx<4096> tmp{0};
#define cn(x) ++tmp.a[S][x]
        for(int S=0;S<msk[m+m];++S)
        {
            int L=i+i;bool A=S&msk[L],B=S&msk[L+1];
            int cs=(S&zsk[L]&zsk[L+1])|(B<<L);
            if(A)cn(cs);
if(i>1   &&!(S&msk[L-3])&&!(S&msk[L-2])&&!(S&msk[L-1])&&A)cn(cs|msk[L-3]|msk[L-2]|msk[L-1]|msk[L+1]);
if(i     &&!(S&msk[L-2])&&!A&&!B)cn(cs|msk[L-2]|msk[L]|msk[L+1]);
if(i>1   &&!(S&msk[L-4])&&!(S&msk[L-2])&&!(S&msk[L-1])&&A&&!B)cn(cs|msk[L-4]|msk[L-2]|msk[L-1]|msk[L]);
if(i!=m-1&&!(S&msk[L+3])&&!A&&!B)cn(cs|msk[L+3]|msk[L]|msk[L+1]);

if(i     &&!(S&msk[L-1])&&A&&!B)cn(cs|msk[L-1]|msk[L]|msk[L+1]);
if(i     &&!(S&msk[L-2])&&!(S&msk[L-1])&&A)cn(cs|msk[L-2]|msk[L-1]|msk[L+1]);
if(i     &&!(S&msk[L-2])&&A&&!B)cn(cs|msk[L-2]|msk[L]|msk[L+1]);
if(i     &&!(S&msk[L-2])&&!(S&msk[L-1])&&A&&!B)cn(cs|msk[L-2]|msk[L-1]|msk[L]);

        }
        xres=mul(xres,tmp);T[i]=tmp;
    }
}
int main()
{
    ll n;int m;scanf("%lld%d",&n,&m);pre(m);--n;res=xres;
    for(;n;xres=mul(xres,xres),n>>=1)if(n&1)res=mul(res,xres);
    printf("%d",res.a[msk[m+m]-1][msk[m+m]-1]);
    return 0;
}

一个充满智慧的想法是，我们注意到最后每个方块都会被填上，令每个未被填满的格子都在填满的格子下面，即状压 DP 时只考虑被填满的连续前缀。这样我们的复杂度是 O(m3^m+27^m\log n) 的，看上去就很能过，但是这个算法对吗？

事实上，这样忽略了某个瓷砖可能先被铺放，而其上的瓷砖后被铺放的情况。但我们并不一定需要完全抛弃这个想法。考虑下图中每一个瓷砖被检查到的位置，哪些情况不会被按序访问到呢？

注意到瓷砖中只有 1 号情况和 6 号情况具有一个位于绿色块位置和瓷砖中的“缝隙”而可以在右侧插入瓷砖(注:没有传新的图，这种做法下那个缝隙在转移中也要求状态中有方块,即也为绿色)，注意到没有能在绿色位置插入，而判定点在这行后面部分的瓷砖。因此有且仅有以下这六种情况不会被计入，因此差不多的写好上面的八种转移后，只要加上下面这六种情况，答案便是完备的了。

由于三进制 DP 难以实现，以及转移的数量较多，手动编写耗时而且容易出错。我们可以使用代码生成器生成代码。生成器和代码如下。

#include<cstdio>
#include<algorithm>
struct data{int a[5][5];};
void deal(data d,int wd=0)
{
    int w=0,h=0;
    for(int i=0;i<5;++i)for(int j=0;j<5;++j)
        if(d.a[i][j])h=std::max(h,i),w=std::max(w,j);
    printf("if(i>%d",(w+=wd)-1);
    if(wd)printf("&&i!=m-1");
    for(int j=0;j<5;++j)for(int i=0;i<5;++i)
        if(d.a[i][j]){printf("&&s[S][i%+d]==%d",j-w,i-h+1+(j>=w));break;}
    printf(")cn(");for(int j=0;j<5;++j)for(int i=4;~i;--i)if(d.a[i][j]){printf("ds[");break;}
    printf("S");for(int j=0;j<5;++j)for(int i=4;~i;--i)if(d.a[i][j]){printf("][i%+d]",j-w);break;}
    for(int j=0;j<5;++j)for(int i=4;~i;--i)if(d.a[i][j]){printf("+pw[i%+d]*%d",j-w,i-h+2+(j>w));break;}
    puts(");");
}
int main()
{
    freopen("c.out","w",stdout);

    deal((data){{{0,1,0},{1,1,1}}});
    deal((data){{{0,1},{1,1},{0,1}}});
    deal((data){{{1,1,1},{0,1,0}}});
    deal((data){{{1,0},{1,1},{1,0}}},-1);
    deal((data){{{0,1},{1,1}}});
    deal((data){{{1,0},{1,1}}});
    deal((data){{{1,1},{0,1}}});
    deal((data){{{1,1},{1,0}}});

    deal((data){{{0,1,1,1},{1,1,1,1}}});
    deal((data){{{0,0,0,1},{0,1,1,1},{1,1,1,1}}});
    deal((data){{{0,1,1,1,1},{1,1,1,1}}});
    deal((data){{{1,1,1},{1,1,1}}});
    deal((data){{{0,0,1},{1,1,1},{1,1,1}}});
    deal((data){{{1,1,1,1},{1,1,1}}});
    return 0;
}

#include<cstdio>
#include<cstring>
typedef long long ll;
typedef unsigned uint;
const uint mod=65521;
template<int n>struct mtrx{uint a[n][n];};
template<int n>
void mul(uint*x,const mtrx<n>&y)
{
    static uint res[n];memset(res,0,n<<2);
    for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(y.a[i][j])
        res[j]=(res[j]+x[i]*y.a[i][j])%mod;
    memcpy(x,res,n<<2);
}
template<int n>
mtrx<n> mul(const mtrx<n>&x,const mtrx<n>&y)
{
    mtrx<n> res{0};
    for(int i=0;i<n;++i)
        for(int k=0;k<n;++k)if(x.a[i][k])
        {
            uint val=x.a[i][k],*x1=res.a[i];const uint*x2=y.a[k];
            for(int j=0;j<n;++j)x1[j]=(x1[j]+x2[j]*val)%mod;
        }
    return res;
}
int s[729][6],ds[729][6],pw[7]={1,3,9,27,81,243,729};
mtrx<729> xres{0},T[6];
void pre(int m)
{
    for(int i=0;i<729;++i)
        for(int x=i,j=0;j<6;++j)
            s[i][j]=x%3,ds[i][j]=i-(x%3)*pw[j],x/=3;
    for(int i=0;i<pw[m];++i)xres.a[i][i]=1;
    for(int i=0;i<m;++i)
    {
        mtrx<729> tmp{0};
#define cn(x) ++tmp.a[S][x]
        for(int S=0;S<pw[m];++S)
        {
            if(s[S][i])cn(S-pw[i]);
if(i>1&&s[S][i-2]==1&&s[S][i-1]==0&&s[S][i+0]==2)cn(ds[ds[ds[S][i-2]][i-1]][i+0]+pw[i-2]*2+pw[i-1]*2+pw[i+0]*2);
if(i>0&&s[S][i-1]==0&&s[S][i+0]==0)cn(ds[ds[S][i-1]][i+0]+pw[i-1]*1+pw[i+0]*2);
if(i>1&&s[S][i-2]==0&&s[S][i-1]==0&&s[S][i+0]==1)cn(ds[ds[ds[S][i-2]][i-1]][i+0]+pw[i-2]*1+pw[i-1]*2+pw[i+0]*1);
if(i>-1&&i!=m-1&&s[S][i+0]==0&&s[S][i+1]==1)cn(ds[ds[S][i+0]][i+1]+pw[i+0]*2+pw[i+1]*2);
if(i>0&&s[S][i-1]==1&&s[S][i+0]==1)cn(ds[ds[S][i-1]][i+0]+pw[i-1]*2+pw[i+0]*2);
if(i>0&&s[S][i-1]==0&&s[S][i+0]==2)cn(ds[ds[S][i-1]][i+0]+pw[i-1]*2+pw[i+0]*2);
if(i>0&&s[S][i-1]==0&&s[S][i+0]==1)cn(ds[ds[S][i-1]][i+0]+pw[i-1]*1+pw[i+0]*2);
if(i>0&&s[S][i-1]==0&&s[S][i+0]==1)cn(ds[ds[S][i-1]][i+0]+pw[i-1]*2+pw[i+0]*1);
if(i>2&&s[S][i-3]==1&&s[S][i-2]==0&&s[S][i-1]==0&&s[S][i+0]==1)cn(ds[ds[ds[ds[S][i-3]][i-2]][i-1]][i+0]+pw[i-3]*2+pw[i-2]*2+pw[i-1]*2+pw[i+0]*2);
if(i>2&&s[S][i-3]==1&&s[S][i-2]==0&&s[S][i-1]==0&&s[S][i+0]==0)cn(ds[ds[ds[ds[S][i-3]][i-2]][i-1]][i+0]+pw[i-3]*2+pw[i-2]*2+pw[i-1]*2+pw[i+0]*2);
if(i>3&&s[S][i-4]==1&&s[S][i-3]==0&&s[S][i-2]==0&&s[S][i-1]==0&&s[S][i+0]==1)cn(ds[ds[ds[ds[ds[S][i-4]][i-3]][i-2]][i-1]][i+0]+pw[i-4]*2+pw[i-3]*2+pw[i-2]*2+pw[i-1]*2+pw[i+0]*1);
if(i>1&&s[S][i-2]==0&&s[S][i-1]==0&&s[S][i+0]==1)cn(ds[ds[ds[S][i-2]][i-1]][i+0]+pw[i-2]*2+pw[i-1]*2+pw[i+0]*2);
if(i>1&&s[S][i-2]==0&&s[S][i-1]==0&&s[S][i+0]==0)cn(ds[ds[ds[S][i-2]][i-1]][i+0]+pw[i-2]*2+pw[i-1]*2+pw[i+0]*2);
if(i>2&&s[S][i-3]==0&&s[S][i-2]==0&&s[S][i-1]==0&&s[S][i+0]==1)cn(ds[ds[ds[ds[S][i-3]][i-2]][i-1]][i+0]+pw[i-3]*2+pw[i-2]*2+pw[i-1]*2+pw[i+0]*1);
        }
        xres=mul(xres,tmp);T[i]=tmp;
    }
}
uint resz[729];
int main()
{
    ll n;int m;scanf("%lld%d",&n,&m);pre(m);resz[pw[m]-1]=1;
    for(;n;xres=mul(xres,xres),n>>=1)if(n&1)mul(resz,xres);
    printf("%d",resz[pw[m]-1]);
    return 0;
}

注意到左右对称的方案可以并为一个状态。也可以从初始状态 dfs 以记录可达状态（例如：一个两格的向下突起，两边都是零格，这就是用这样的瓷砖铺不出来的）并删除其他转移，可以减小矩阵大小，进一步加快速度。

课后习题：(带输入障碍)俄罗斯方块铺设矩形计数如何用类似的方法做到 O(n4^m)？