疯狂BB的ZY

题目描述

zy 超强,总是想些奇怪的问题。
一天,他脑洞出了这样一个问题。有$n$个点,没个点的度数不超过 Ai, 问从中选出一些点形成一颗大小为 $s(1 \leq s \leq n)$ 的树的方案数。zy 自然 O(n)秒掉了这题,于是他想用这个问题考考你,来显示自己的强大。

数据范围

对于$20\%$的数据: $n \leq 6$

对于$60\%$的数据: $n \leq 50$

对于 $100\%$的数据: $n \leq 100$

样例输⼊

1
2
3
2 2 1

样例输出

1
3 3 2

输⼊描述

第一行有一个整数$n$.
第二行$n$个数表示$A_i​$.

题解

考虑$n$个点的生成树是一个长度为$n-2$的prufer序列,其中第$i$个点出现的次数小于$A_i$次。

设$f[i][j][k]$表示前$i$个点,有$j$个在树上,其prufer序列长度为k的方案数。

考虑两种转移,$i$不选和$i$选,我们可以枚举$i$这个点出现几次。

$$
f[i][j][k]=f[i-1][j][k]+\sum_{t=0}^{k}\binom{k}{t}f[i-1][j-1][k-t] \\
ans=f[n][i][i-2]
$$

这样做的复杂度为$O(n^4)$。

考虑把$f[i][j]$看做指数生成函数,那么从$f[i-1][j-1]$转移的时候因为对应系数要乘上一个组合数,可以看做$f[i-1][j-1]$和$C(i)=\sum_{1}^{A[i]-1}\frac{1}{k!}x^k$这个生成函数的卷积。

然后NTT就可以$O(n^3 logn)$了。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IL inline
IL ll read() {
char ch = getchar(); ll u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
#define rep(i, j, k) for (int(i) = (j); (i) <= (k); ++(i))
#define dep(i, j, k) for (int(i) = (j); (i) >= (k); --(i))
const int maxn = 105;
int C[maxn][maxn], f[maxn][maxn][maxn], a[maxn];
const int mod = 1004535809;
IL void add(int &x, int y) { x += y; x = (x >= mod ? x - mod : x); }
IL int pls(int x, int y) { x += y; return x >= mod ? x - mod : x; }
IL int mul(int x, int y) { return 1ll * x * y % mod; }
int main() {
freopen("zy.in", "r", stdin);
freopen("zy.out", "w", stdout);
C[0][0] = C[1][0] = C[1][1] = 1;
for (int i = 2; i <= 100; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j)
C[i][j] = pls(C[i - 1][j], C[i - 1][j - 1]);
}
int n = read();
rep(i, 1, n) a[i] = read();
f[0][0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= i; ++j) for (int k = 0; k <= n; ++k) {
add(f[i][j][k], f[i - 1][j][k]);
if (j != 0) {
for (int t = 0; t < a[i] && t <= k; ++t) {
add(f[i][j][k], mul(C[k][t], f[i - 1][j - 1][k - t]));
}
}
}
}
cout << n << " ";
rep(i, 2, n) printf("%d ", f[n][i][i - 2]);
return 0;
}