生成负次幂的一种解决办法。
题意:给定每个点的度数,任选一些点使得他们能组成一棵树。$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$,令人震惊。
1 | int main() |