Loj 3246 Cave Paintings

Posted on | Views:

树形 dp.

一个直接的想法是,若 $x$ 的水能流到 $y$ ,就连边 $x\to y$ ,若某个点有水,则它的全部后继也都有水.

直接建图的边数很爆炸,且只是一张普通的有向图,没有足够优秀的性质支持我们统计方案数,考虑对建图进行优化.

首先可以把同一行中,能通过本行及下方的点四连通的点缩在一起,它们的方案一定是一样的.

缩点后,连边时可以只连相邻两行之间的边,不难发现原来的所有限制可以通过传递得到,方案数不变.

此时图变成了一个有向森林,做简单的树形 dp 即可统计方案数,可以不显式建树,用并查集维护即可.

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 1e3 + 10, M = 1e6 + 10;
int n, m, cnt = 0, id[N][N], dp[M], fa[M], ans = 1;
int Find(int x)
{
	return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
char buf[N][N];
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; ++i)
		scanf("%s", buf[i] + 1);
	for (int i = n - 1; i >= 2; --i)
	{
		int lst = cnt;
		for (int j = 2; j <= m - 1; ++j)
			if (buf[i][j] == '.')
			{
				if (buf[i][j - 1] == '#')
					dp[++cnt] = 1, fa[cnt] = cnt;
				id[i][j] = cnt;
				if (buf[i + 1][j] == '.')
				{
					int tmp = Find(id[i + 1][j]);
					if (tmp != cnt)
					{
						dp[cnt] = mul(dp[cnt], dp[tmp]);
						fa[tmp] = cnt;
					}
				}
			}
		for (int j = lst + 1; j <= cnt; ++j)
			if (Find(j) == j)
				inc(dp[j], 1);
	}
	for (int i = 1; i <= cnt; ++i)
		if (Find(i) == i)
			ans = mul(ans, dp[i]);
	write(ans, '\n');
	return 0;
}