1 条题解

  • 0
    @ 2025-8-24 22:40:55

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Edward1002001
    这个家伙很菜，什么也没有留下

    搬运于2025-08-24 22:40:55，当前版本为作者最后更新于2023-12-22 11:13:11，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

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

    一个显然的想法是，记前两行的瓷砖有无状态，在铺放瓷砖的某个固定位置检测瓷砖所应该占有的地方有无方块，并将其使用矩阵转移，这样的做法是 O(m4m+64mlog⁡n)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(m3m+27mlog⁡n)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(n4m)O(n4^m)？

    • 1

    [蓝桥杯 2015 国 A] 铺瓷砖

    信息

    ID
    5947
    时间
    5000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 34ms