「ZJOI2009」多米诺骨牌 - 状压动规/轮廓线DP+容斥原理 | Bill Yang's Blog
0%

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

题目大意

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


题目分析

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

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

好像做完了。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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;
}
姥爷们赏瓶冰阔落吧~