「ZJOI2009」多米诺骨牌 - 状压动规/轮廓线DP+容斥原理

题目大意

    有一个$n\times m$的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些$1\times2$或者$2\times1$的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意你并不需要放满所有没有障碍的格子。

---

题目分析

我们先容斥一下，对列进行容斥，转化为至少有$k$列之间不横跨的问题，这样我们将棋盘分为了列独立的几个连通块。
现在来考虑行的限制，我们再容斥一下将问题转化为总数$-$有至少一行不横跨的问题。
设$g(i)$为前$i$行合法的方案数，$h(u,d,l,r)$为在矩阵$[u,d,l,r]$中任意放骨牌的方案数。

$$g(i)=\prod_{列连通块}h[1,i,l,r]-\sum_{j=1}^{i-1}\prod_{列连通块}h[j+1,i,l,r]$$

现在的问题转化为求解$h[u,d,l,r]$。
很显然，这是一个简单的插头DP，更准确地说其实是一个简单的轮廓线DP。
我们逐格考虑，根据当前格子和上方和左方的放置情况，可以放置骨牌转化到新状态。
这部分见代码吧。
至于时间复杂度，直接估为$n^5\cdot2^n$时不准确的，用计数器算了一下，在不算常数的情况下跑了$2$亿次。

好像做完了。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=17,maxs=1<<16,mod=19901013;

int n,m,a[maxn][maxn],bit[maxn],bitnum[maxs],f[maxn][maxn][maxs],g[maxn],h[maxn][maxn][maxn][maxn],ans=0;

void check(int &x) {if(x>=mod)x-=mod;if(x<0)x+=mod;}
void add(int &x,int v) {x+=v;check(x);}
void mul(int &x,int v) {x=1ll*x*v%mod;}

void Dp() {
	for(int u=1; u<=n; u++)
		for(int l=1; l<=m; l++)
			for(int r=l; r<=m; r++) {
				int lim=bit[r-l+1];
				for(int S=0; S<lim; S++)f[u][l][S]=0;
				f[u][l][0]=1;
				for(int x=u; x<=n; x++) {
					for(int y=l; y<=r; y++) {
						for(int S=0; S<lim; S++)f[x][y+1][S]=0;
						for(int S=0; S<lim; S++)
							if(f[x][y][S]) {
								add(f[x][y+1][S&(~bit[y-l])],f[x][y][S]); //不放
								if(y>l&&a[x][y-1]&&a[x][y]&&!(S&bit[y-l-1]))add(f[x][y+1][S|bit[y-l]|bit[y-l-1]],f[x][y][S]); //横放
								if(x>u&&a[x-1][y]&&a[x][y]&&!(S&bit[y-l]))add(f[x][y+1][S|bit[y-l]],f[x][y][S]); //竖放
							}
					}
					for(int S=0; S<lim; S++)add(h[u][x][l][r],f[x+1][l][S]=f[x][r+1][S]);
				}
			}
}

char s[maxn];

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=0; i<=max(n,m); i++)bit[i]=1<<i;
	for(int i=1; i<=n; i++) {
		scanf("%s",s+1);
		for(int j=1; j<=m; j++)
			if(s[j]=='.')a[i][j]=1;
			else a[i][j]=0;
	}
	Dp();
	for(int S=0; S<bit[m]; S++)bitnum[S]=bitnum[S>>1]+(S&1);
	for(int S=0; S<bit[m-1]; S++) {
		memset(g,0,sizeof(g));
		g[0]=1;
		vector<int> c;
		for(int i=1; i<m; i++)if(S&bit[i-1])c.push_back(i);
		for(int u=1; u<=n; u++)
			for(int x=0; x<u; x++) {
				int now=1,l=1;
				for(int r:c) {
					mul(now,h[x+1][u][l][r]);
					l=r+1;
				}
				if(l<=m)mul(now,h[x+1][u][l][m]);
				if(x>0)add(g[u],mod-1ll*g[x]*now%mod);
				else add(g[u],1ll*g[x]*now%mod);
			}
		if(bitnum[S]&1)add(ans,mod-g[n]);
		else add(ans,g[n]);
	}
	printf("%d\n",ans);
	return 0;
}