Code+三月月赛 Div1 D 白金元首与莫斯科（插头dp）

发表于 |
字数统计: 827字 | 阅读时长 ≈ 5min

[CODE+]白金元首与莫斯科

题面

如果说障碍格子已经确定，那么可以用一个简单的插头dp算出方案数。
那么可以暴力枚举障碍格子，但这样是$O(n^2m^22^m)$的。

注意到由于不确定的状态格子只有一个，因此可以从左上到右下dp一次，再从右下到左上dp一次，令两次的dp数组分别为$F1[i][j][S]$和$F2[i][j][S]$，那么当$(x,y)$为障碍时，答案就是$\sum F1[i][j-1][S1]\times F2[i][j+1][S2]$，$S1$和$S2$满足轮廓线上对应位置要么都有插头，要么都没有。如果在记录状态的时候都记录在当前坐标位置，那么就是$S1=S2$，注意到$(x,y)$这个点的上下左右四个方向都不能有插头。
复杂度$O(nm2^m)$

代码：

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod=1e9+7;
int n,m,map[20][20];
int S,F1[20][20][1<<18],F2[20][20][1<<18],Ans[20][20];
void add(int &x,int y){x+=y;x-=x>=mod?mod:0;}
int mul(int x,int y){return 1ll*x*y%mod;}
void PlugDP1()
{
	int l,u,*p,*q;
	F1[0][m][0]=1;
	for(register int i=1;i<=n;i++)
	{
		p=F1[i][0];q=F1[i-1][m];
		for(register int j=0;j<=(S>>1);j++)add(p[j<<1],q[j]);
		for(register int j=1;j<=m;j++)
		{
			p=F1[i][j];q=F1[i][j-1];
			for(register int k=0;k<=S;k++)
			if(q[k])
		    {
		    	l=(k>>j-1)&1;u=(k>>j)&1;
		    	if(!map[i][j])
		    	{
		    		if(!l&&!u)add(p[k],q[k]);
		    	}
		    	else
		    	{
		    		if(!l&&!u)
		    		{
		    			add(p[k],q[k]);
		    			if(map[i+1][j])add(p[k|(1<<j-1)],q[k]);
		    			if(map[i][j+1])add(p[k|(1<<j)],q[k]);
		    		}
		    		else if(!l&&u)add(p[k^(1<<j)],q[k]);
		    		else if(l&&!u)add(p[k^(1<<j-1)],q[k]);
		    	}
		    }
		}
	}
}
void PlugDP2()
{
	int r,d,tmp,*p,*q;
	F2[n+1][1][0]=1;
	for(register int i=n;i>=1;i--)
	{
		p=F2[i][m+1];q=F2[i+1][1];
		for(register int j=0;j<=S;j++)add(p[j>>1],q[j]);
		for(register int j=m;j>=1;j--)
		{
			p=F2[i][j];q=F2[i][j+1];
			for(register int k=0;k<=S;k++)
			if(q[k])
		    {
		    	r=(k>>j)&1;d=(k>>j-1)&1;
		    	if(!map[i][j])
		    	{
		    		if(!r&&!d)add(p[k],q[k]);
		    	}
		    	else
		    	{
		    		if(!r&&!d)
		    		{
		    			add(p[k],q[k]);
		    			if(map[i-1][j])add(p[k|(1<<j)],q[k]);
		    			if(map[i][j-1])add(p[k|(1<<j-1)],q[k]);
		    		}
		    		else if(r&&!d)add(p[k^(1<<j)],q[k]);
		    		else if(!r&&d)add(p[k^(1<<j-1)],q[k]);
		    	}
		    }
		}
	}
}
int main()
{
	int x,y,l,r,u,d,*p,*q;
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
	for(register int j=1;j<=m;j++)scanf("%d",&map[i][j]),map[i][j]^=1;
	S=(1<<m+1)-1;
	PlugDP1();PlugDP2();
	for(register int i=1;i<=n;i++)
	for(register int j=1;j<=m;j++)
	{
		if(!map[i][j])continue;
		p=F1[i][j-1];q=F2[i][j+1];
		for(register int k=0;k<=S;k++)
		if(p[k]&&q[k])
	    {
	    	l=(k>>j-1)&1;u=(k>>j)&1;
	    	if(!l&&!u)add(Ans[i][j],mul(p[k],q[k]));
		}
	}
	for(register int i=1;i<=n;i++,puts(""))
	for(register int j=1;j<=m;j++)printf("%d ",Ans[i][j]);
}