Luogu P5219 无聊的水题 I

prufer 序列 + 多项式重工业。

题意：求有多少棵大小为 $n$ 的有根树满足最大度数为 $m$。$n\le 5\times {10}^4$，$m\le n$。

最大点度数为 $m$，显然可以转化为最大点度数 $\ge m$ 减去最大点度数 $\le m-1$ 的方案数。下面仅计算 $\le m$ 的情况。

树的计数的常用两个手段是 Matrix-Tree 矩阵树定理和 prufer 序列。考虑使用 prufer 序列计算。由于度数等于出现次数 +1，于是我们只需要限定每一个点的出现次数 $<m$ 即可。

由于是同一个点出现多次只算一种方案，考虑使用 EGF，然后直接计算他的 $n$ 次方即可。直接使用倍增快速幂即可通过，似乎没必要使用什么 $\ln /\exp$ 的方法。

时间复杂度 $O(n{\log }^{2}n)$ 或 $O(n\log n)$。并不卡常。

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;
}