Luogu P5860 Counting Trees

生成负次幂的一种解决办法。

题意：给定每个点的度数，任选一些点使得他们能组成一棵树。$n\leq 5\times 10 ^ 5$，6s。

首先给出结论：

$n$ 个点能组成树的充要条件是 $n$ 个点的度数和为 $2n - 2$（每个点度数 $\geq 1$）。

必要性易得。充分性可以发现一个点的最大度数为 $n - 1$，不可能多出来度数没有连。严谨证明可以考虑 prufer 序列，但我不会。

由于 $n$ 并没有定，我们需要把 $2n - 2$ 拆给每一个数，于是对每一个数度数 -2，于是我们需要求的就是 $\prod(1 + x ^ {d_i - 2})$ 的 $x ^ {-2}$ 的系数。

负数没学过什么卷积，于是可以考虑正负各自卷积，最后倒过来合并。0 次项最后当常数乘上去即可。

容易发现负次幂只有 -1，假设有 $m$ 个，容易发现多项式已经确定，为 $\sum_{i = 0} ^ m \binom mix ^ {-i}$。下面考虑正次幂的计算。

看似我们可以 FFT，但是每个多项式虽然只有两个非零项，但是次数很高，无法计算。

还是考虑先取 $\ln$，于是我们需要计算 $\ln(1 + x ^ d)$（默认已经减了 2）。$\ln$ 可以展开得到：$-\sum_{i = 1} \dfrac{(-x) ^ {di}}i$。这个式子可以把相同的 $d$ 一起计算，容易得到复杂度为 $O(n\ln n)$。然后 $\exp$ 回去即可得到乘起来的式子。

最后我们把负的翻转到正次幂，卷积一下平移回去即可得到。在这里我们需要平移 $m$ 位，于是最后输出 $x ^ {m - 2}$ 的次数即可。注意乘上度数为 2 的贡献，为 $2 ^ {cnt}$。

总时间复杂度 $O(n\log n)$，$\exp$ 这么大常数的东西居然能在 500ms 左右跑 $5\times 10 ^ 5$，令人震惊。

int main()
{
	init();
	int n;
	std::cin >> n;
	poly cnt(n + 1);
	for (int i = 1, v; i <= n; ++ i) scanf("%d", &v), cnt[v] ++;
	int m = cnt[1], pw = cnt[2];
	if (m < 2) return puts("0"), 0;
	poly f(m - 1), g(m + 1);
	for (int i = 1; i <= m - 2; ++ i)
	{
		int v = cnt[i + 2];
		for (int j = 1, op = 1; j * i + 1 < m; ++ j, op = Mod - op)
			f[i * j] = (f[i * j] + (LL) op * v % Mod * inv[j]) % Mod;
	}
	f = Exp(f);
	for (int i = 0; i <= m; ++ i) g[i] = C(m, i);
	f = f * g;
	int res = (LL) f[m - 2] * qpow(2, pw) % Mod;
	printf("%d\n", res);
	return 0;
}