Loj 6094 归乡迷途

Posted on | Views:

bfs 树 + dp 计数问题.

限制可以简单归纳为,图的 bfs 树中,每个点的父亲编号小于自己,且非树边只在同一深度的点间出现.
对 bfs 树进行 dp, 每一层加入的数都一定是编号连续的一段,并且只需要记录上一层的信息就可以转移.

设 $f(i,j)$ 表示考虑了前 $i$ 个点,最深的一层有 $j$ 个点,前 $i-j$ 个点度数已经满足限制,最后 $j$ 个点只考虑向父亲连边.
设 $g(i,j,k)$ 表示上一层有 $j$ 个点度数要求为 $2$ , $k$ 个点度数要求为 $3$ ,这层有 $i$ 个点时的拼接以及上一层内部连边.
枚举上一层有 $k$ 个点,有 $f(i,j)=\sum_{k\le i-j}f(i-j,k)\cdot g(j,c_2,c_3)$ , $c_2,c_3$ 表示 $k$ 个点中要求度数为 $2,3$ 的点,由于它们都各自向父亲连了一条边,实际上还需要连的边数是 $1,2$ .

考虑如何计算转移系数 $g(i,j,k)$ .

当 $i>0​$ 时,考虑该层第一个点的父亲是哪个点,有
$$
g(i,j,k)=j\cdot g(i-1,j-1,k)+k\cdot g(i-1,j+1,k-1)
$$

当 $i=0$ 时,此时需要在上一层内互相连边,使得它们满足度数限制,此时再分 $j>0$ 和 $j=0$ 讨论.

当 $i=0,j>0$ 时,枚举第一个还要连 $1$ 条边的点连的哪个点,有
$$
g(0,j,k)=(j-1)\cdot g(0,j-2,k)+k\cdot g(0,j,k-1)
$$

当 $i=j=0$ 时, $k$ 个点都要连 $2$ 条边,一定是若干个互不相交的,大小 $>2$ 的环,这里犯不着 $\exp$ ,暴力预处理即可.

最后答案就是 $\sum f(n,i)\cdot g(0,c_2,c_3)$ ,时间复杂度 $O(n^3)$ .

注意根节点没有向父亲连的边,儿子方向上的度数不会 $-1​$ ,需要特判一下,即先将前两层的 $f​$ 单独算出来.

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
102
103
104
105
106
107
108
109
110
111
112
113
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define y1 ysgh
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 = 300 + 10;
int n, d[N], f[N][N], g[N][N][N], dp[N], fac[N], binom[N][N], c2, c3, ans = 0;
int main()
{
	n = read();
	binom[0][0] = 1, fac[0] = (P + 1) >> 1;
	for (int i = 1; i <= n; ++i)
	{
		fac[i] = mul(fac[i - 1], i);
		d[i] = read();
		binom[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			binom[i][j] = add(binom[i - 1][j - 1], binom[i - 1][j]);
	}
	dp[0] = 1;
	for (int i = 3; i <= n; ++i)
		for (int j = 3; j <= i; ++j)
			inc(dp[i], mul(mul(fac[j - 1], dp[i - j]), binom[i - 1][j - 1]));
	for (int i = 0; i <= n; ++i)
		for (int j = 0; i + j <= n; ++j)
			for (int k = 0; i + j + k <= n; ++k)
			{
				if (i == 0)
				{
					if (j == 0)
						g[i][j][k] = dp[k];
					else
					{
						if (j >= 2)
							inc(g[i][j][k], mul(j - 1, g[i][j - 2][k]));
						if (k >= 1)
							inc(g[i][j][k], mul(k, g[i][j][k - 1]));
					}
				}
				else
				{
					if (j >= 1)
						inc(g[i][j][k], mul(j, g[i - 1][j - 1][k]));
					if (k >= 1)
						inc(g[i][j][k], mul(k, g[i - 1][j + 1][k - 1]));
				}
			}
	f[1 + d[1]][d[1]] = 1;
	for (int i = d[1] + 2; i <= n; ++i)
	{
		for (int j = 1; j <= i - d[1] - 1; ++j)
		{
			c2 = c3 = 0;
			for (int k = 1; j + k <= i - 1; ++k)
			{
				if (d[i - j - k + 1] == 2)
					++c2;
				else
					++c3;
				inc(f[i][j], mul(f[i - j][k], g[j][c2][c3]));
			}
		}
	}
	c2 = c3 = 0;
	for (int i = 1; i < n; ++i)
	{
		if (d[n - i + 1] == 2)
			++c2;
		else
			++c3;
		inc(ans, mul(f[n][i], g[0][c2][c3]));
	}
	cout << ans << '\n';
	return 0;
}