prufer 序列 + 多项式重工业。
题意：求有多少棵大小为 $n$ 的有根树满足最大度数为 $m$。$n\leq 5\times 10 ^ 4$，$m\leq n$。
最大点度数为 $m$，显然可以转化为最大点度数 $\geq m$ 减去最大点度数 $\leq m - 1$ 的方案数。下面仅计算 $\leq m$ 的情况。
树的计数的常用两个手段是 Matrix-Tree 矩阵树定理和 prufer 序列。考虑使用 prufer 序列计算。由于度数等于出现次数 +1，于是我们只需要限定每一个点的出现次数 $<m$ 即可。
由于是同一个点出现多次只算一种方案，考虑使用 EGF，然后直接计算他的 $n$ 次方即可。直接使用倍增快速幂即可通过，似乎没必要使用什么 $\ln/\exp$ 的方法。
时间复杂度 $O(n\log ^ 2n)$ 或 $O(n\log n)$。并不卡常。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int solve(int lim)
{
if (lim <= 0) return 0;
poly bs(lim + 1, 1), res(1, 1);
for (int i = 0; i <= lim; ++ i) bs[i] = (LL) bs[i] * infact[i] % Mod;
int k = n;
for (; k; k >>= 1, bs = bs * bs, bs.resize(std::min((int) bs.size(), n - 1)))
if (k & 1) res = res * bs, res.resize(std::min((int) res.size(), n - 1));
return res[n - 2] * (LL) fact[n - 2] % Mod;
}
int main()
{
init();
int m, res;
std::cin >> n >> m;
printf("%d\n", adj(res = solve(m - 1) - solve(m - 2)));
return 0;
}
|