比较套路的二项式反演 + 树形 DP。
题意：给定 $n$ 个点的根为 1 的树，现在你要为 $n$ 个点赋上一个 $[1, D]$ 的值，儿子权值不能超过父亲。问合法的赋值方案。$n\leq 3000, D\leq 10 ^ 9$，对 $10 ^ 9 + 7$ 取模。
看样子是 $O(n ^ 2)$ 的做法。
虽然朴素 DP 是 $O(nD)$ 的（前缀和优化），但是我们发现这样其实真正用到的元素一定不超过 $n$ 个，如果记 $f(x)$ 为所有权值恰好有 $x$ 个不同的，那么答案可以写作：
这个式子容易 $O(n)$ 计算，现在问题转化为求 $f(x)$。
我们仍然按照朴素 DP 的方式，但值域仅为 $[1, n]$，这样一定是 $O(n ^ 2)$ 的，记 $g(x)$ 为我们最后得到的 DP 数组，其意义为最大值为 $x$ 的方案数。
按照组合意义拆分，容易得到：
容易二项式反演得到：
这样就可以 $O(n ^ 2)$ 计算了。
另外，这个式子也可以简单容斥：
这样就可以 $O(n ^ 2)$ 计算了。
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
| int main()
{
std::cin >> n >> D;
infact[1] = infact[0] = 1;
for (int i = 2; i <= n; ++ i)
infact[i] = (LL) infact[Mod % i] * (Mod - Mod / i) % Mod;
for (int i = 2; i <= n; ++ i) infact[i] = (LL) infact[i] * infact[i - 1] % Mod;
for (int i = C[0][0] = 1; i <= n; ++ i)
for (int j = C[i][0] = 1; j <= i; ++ j)
adj(C[i][j] = C[i - 1][j - 1] + C[i - 1][j] - Mod);
for (int i = 2; i <= n; ++ i) scanf("%d", f + i);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j) dp[i][j] = 1;
for (int i = n; i > 1; -- i)
{
for (int j = 1; j <= n; ++ j) adj(s[i][j] = s[i][j - 1] + dp[i][j] - Mod);
for (int j = 1; j <= n; ++ j)
dp[f[i]][j] = dp[f[i]][j] * (LL) s[i][j] % Mod;
}
static int g[N];
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= i; ++ j)
if (!((i - j) & 1)) g[i] = (g[i] + dp[1][j] * (LL) C[i - 1][j - 1]) % Mod;
else g[i] = (g[i] + (Mod - dp[1][j]) * (LL) C[i - 1][j - 1]) % Mod;
int res = 0, dn = 1;
for (int i = 1; i <= n && i <= D; ++ i)
{
dn = dn * (LL) (D - i + 1) % Mod;
res = (res + (LL) dn * infact[i] % Mod * g[i]) % Mod;
}
std::cout << res << std::endl;
return 0;
}
|