自动搬运

查看原文

来自洛谷，原作者为

	hwk0518 **

搬运于2025-08-24 21:39:26，当前版本为作者最后更新于2019-02-26 21:06:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题还是比较好想的，就是细节多了一些。

网上的题解大部分都是插头$DP$，我来写一份状压+容斥的题解。

首先考虑没有限制的情况，即，用$1*2$的骨牌覆盖整个网格图，有多少种不同的方案？

考虑按照

$(1,1),(1,2),...,(1,m),(2,1),...,(2,m),...,(n,1),...,(n,m)$

的顺序加点。加入$(i,j)$时统计用骨牌覆盖$(i-1,j)(i,j)$和覆盖$(i,j-1)(i,j)$的方案数，以及不覆盖$(i,j)$的方案数。我们需要知道$(i-1,j)$和$(i,j-1)$的信息。

但是$(i-1,j+1),...,(i-1,m),(i,1),...,(i,j-2)$之后还可能和某个$(i,j)$一上一下地用骨牌覆盖，所以也要记下来。用一个状压维护。

更进一步，我们考虑对所有网格图的所有子矩阵求出没有限制的答案（之后有用）。设左上角为$(x_1,y_1)$，右下角为$(x_2,y_2)$的矩阵的答案是$dp[y_1][x_1][y_2][x_2]$。（行列颠倒后转移会更简便。）在求解$dp[y_1][x_1][y_2][n]$的过程中，我们一定有某个时刻记录了$(k,y_1),(k,y_1+1),...,(k,y_2)$的状态。将所有状态的$DP$值加起来就是$dp[y_1][x_1][y_2][k]$。所以只要枚举$y_1,x_1,y_2$求解即可。

现在考虑有限制的情况。想到容斥。比较流行的容斥有两种：

$(1)$子集容斥。

$(2)$代表元容斥。即，为了求出让条件$1,2,...,n$均满足的情况数，我们可以枚举不满足的条件中编号最小的那一个。

都用子集容斥显然不行。因为复杂度是$2^{n+m}$。都用代表元容斥也不行。因为枚举了第一个没有横跨的行后，求的实际上是分割线上边和下边均有列横跨的方案数。而我们要求的是分割线上边和下边至少有一个有列横跨的方案数。

所以对列用容斥，行用代表元。枚举哪些列的夹缝没有横跨，它们将矩阵分为若干块。记$f_i$表示前$i$行的矩阵合法的方案数。$g[i][j]$表示$i$行到$j$行任意摆放且不横跨夹缝的方案数。则有：

$g[i][j]=\prod_{x=1}^k dp[l_x][i][r_x][j]$

其中$l_t$表示第$t$块的左端点。$r_t$亦然。

$f[i]=g[1][i]-\sum_{j=2}^{i}f[j-1]*g[j][i]$

这样，求出每个子集的$f_n$，子集容斥即可。

时间复杂度方面，一开始的预处理主要瓶颈在状压。它是指数级别的。最坏情况下是$2^m$。有$n$次会取到。每次要枚举$n*n$个点。时间复杂度$O(2^m*n^3)$。至于其他不能取到最坏复杂度的情况，由于复杂度不同级，可以略去。

后面的统计，子集容斥一次$O(2^m)$，代表元容斥一次$O(n)$，故时间复杂度为$O(2^m*n)$

总时间复杂度是$O(2^m*n^3)$。

很多人说我题解写得太详细是在浪费时间。用某学姐的话说，“好像在谈恋爱”。但我想，题解不仅是个人的总结，更是对其他人的帮助。这道题网络上有很多题解，但大多数都是三言两语就带过，很难看懂。不仅这道题，很多题也是一样。而我所做的，就是将我的理解，通过通俗易懂的方式，呈现给大家。能用短暂的两三年$OI$生涯，为更多$OIer$造福，我感到很欣慰。这就是所谓的“前人栽树，后人乘凉”。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

const int N=15;
const int T=1<<N;
const int mod=19901013;
int n,m,pre[N][N][N][N],tdp[2][T],ans;
int f[N],tl,cnt[T];
pair<int,int> lis[N];
char s[N][N];

namespace MATHEMATICS
{
	int add(int x,int y)
	{
		int ret=x+y;
		if(ret>=mod) ret-=mod;
		return ret;
	}
	int mi(int x,int y)
	{
		int ret=x-y;
		if(ret<0) ret+=mod;
		return ret;
	}
	
	void inc(int &x,int y)
	{
		x+=y;
		if(x>=mod) x-=mod;
	}
	void dec(int &x,int y)
	{
		x-=y;
		if(x<0) x+=mod;
	}
	
	int mul(int x,int y)
	{
		return 1LL*x*y%mod;
	}
}
using namespace MATHEMATICS;

void init()
{
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;++i) scanf("%s",&s[i]);
}

void cal(int xu,int yu,int xd)
{
	int i,j,S,mxS=1<<xd-xu+1;
	int oldpos=0,newpos=1;
	for(S=0;S<mxS;++S) tdp[0][S]=0;
	tdp[0][mxS-1]=1;
	
	for(i=yu;i<n;++i)
		for(j=xu;j<=xd;++j)
		{
			for(S=0;S<mxS;++S) tdp[newpos][S]=0;
			for(S=0;S<mxS;++S)
			{
				if(!tdp[oldpos][S]) continue;
				if(!(S&(1<<xd-xu))&&s[i][j]=='.'&&s[i-1][j]=='.')
					inc(tdp[newpos][(S<<1)&(mxS-1)|1],tdp[oldpos][S]);
				if(!(S&1)&&s[i][j]=='.'&&j>xu&&s[i][j-1]=='.')
					inc(tdp[newpos][(S<<1)&(mxS-1)|3],tdp[oldpos][S]);
				inc(tdp[newpos][(S<<1)&(mxS-1)],tdp[oldpos][S]);
			}
			if(j==xd)
			{
				for(S=0;S<mxS;++S)
					inc(pre[xu][yu][xd][i],tdp[newpos][S]);
			}
			oldpos^=1,newpos^=1;
		}
}

void prework()
{
	int i,j,k;
	for(i=0;i<m;++i)
		for(j=0;j<n;++j)
			for(k=i;k<m;++k)
				cal(i,j,k);
}

int calc(int S)
{
	int i,j,k,las=0;tl=0;
	for(i=0;i<m-1;++i)
		if((1<<i)&S)
			lis[++tl]=make_pair(las,i),las=i+1;
	lis[++tl]=make_pair(las,m-1);
			
	for(i=0;i<n;++i)
	{
		f[i]=1;
		for(j=1;j<=tl;++j)
			f[i]=mul(f[i],pre[lis[j].first][0][lis[j].second][i]);
		for(k=0;k<i;++k)
		{
			int now=f[k];
			for(j=1;j<=tl;++j)
				now=mul(now,pre[lis[j].first][k+1][lis[j].second][i]);
			dec(f[i],now);
		}
	}
	
	return f[n-1];
}

void work()
{
	int ans=0,S,mxS=1<<m-1;
	for(S=0;S<mxS;++S) cnt[S]=cnt[S>>1]+(S&1);
	for(S=0;S<mxS;++S)
	{
		if(cnt[S]&1) dec(ans,calc(S));
		else inc(ans,calc(S));
	}
	printf("%d\n",ans);
}

int main()
{
	init();prework();work();
	return 0;
}