做的时候把两部分拆开了导致失去了统一性，实际上不分开做就有简洁优美的做法了。
首先转化题意：限制相当于在 BFS
树上，每层都是一段编号连续的区间，且原图只有 BFS
树上向父亲连的边以及同层点之间连的边。
那么我们考虑逐层 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
| #include <bits/stdc++.h>
using namespace std;
const int N = 55,P = 1e9 + 7,inv2 = (P + 1) / 2;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,d[N];
int g[N][N][N];
int h[N][N][N][N];
int fac[N],ifac[N];
int sd2[N],sd3[N];
int dp[N][N];
inline void init(int n) {
fac[0] = 1;
for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[1] = 1;
for(int i = 2;i <= n;i++) ifac[i] = 1ll * (P - P / i) * ifac[P % i] % P;
ifac[0] = 1;
for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % P;
}
inline int C(int n,int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int main() {
cin >> n;
for(int i = 1;i <= n;i++) cin >> d[i];
for(int i = 1;i <= n;i++)
sd2[i] = sd2[i - 1] + (d[i] == 2),
sd3[i] = sd3[i - 1] + (d[i] == 3);
init(n);
g[0][0][0] = 1;
for(int k = 3;k <= n;k++)
for(int l = 2;l < k;++l)
Plus(g[0][0][k],1ll * g[0][0][k - l - 1] * C(k - 1,l) % P * fac[l] % P * inv2 % P);
for(int i = 0;i <= n;i++)
for(int k = 0;k <= n;k++)
for(int j = 0;j <= n;j++) {
if(!i && !j) continue;
if(i == 0) {
if(j >= 2) Plus(g[i][j][k],1ll * (j - 1) * g[i][j - 2][k] % P);
Plus(g[i][j][k],1ll * k * g[i][j][k - 1] % P);
} else {
if(j) Plus(g[i][j][k],1ll * g[i - 1][j - 1][k] * j % P);
if(k) Plus(g[i][j][k],1ll * g[i - 1][j + 1][k - 1] * k % P);
}
}
dp[2][d[1] + 1] = 1;
for(int i = d[1] + 1;i <= n;i++) {
for(int j = 1;j <= i;j++)
for(int k = i + 1;k <= n;k++)
Plus(dp[i + 1][k],1ll * dp[j][i] * g[k - i][sd2[i] - sd2[j - 1]][sd3[i] - sd3[j - 1]] % P);
}
int ans = 0;
for(int i = 1;i <= n;i++)
Plus(ans,1ll * dp[i][n] * g[0][sd2[n] - sd2[i - 1]][sd3[n] - sd3[i - 1]] % P);
cout << ans << endl;
return 0;
}
|