4002 题解

我来胡一个 $O(n\log^2n)$ 做法。 考虑用 Prufer 序列去对应树，设 $d_i$ 表示 $i$ 在 Prufer 序列中出现的次数，则有 $\sum d_i = n - 2$。 考虑度数序列 $d$ 造成的贡献是： $$\frac{(n-2)!}{\prod d_i!}\prod(d_i+1)^ma_i^{d_i+1}\sum (d_i+1)^m$$ $$=(n-2)!\prod a_i \sum_j \frac{1}{\prod d_i!} \prod a_i^{d_i}\prod_{i\ne j}(d_i+1)^m (d_j+1)^{2m}$$ 这前面的 $(n-2)!\prod a_i$ 是常数，只考虑后面的这个 $\sum$。 设后面这个 $\sum$ 关于 $\sum d_i$ 的生成函数是 $F(x)$。 我们看到每一个 $d_i$ 造成的贡献是 $\frac{1}{d_i!} a_i^{d_i}(d_i+1)^m$ 或者最后一个幂次是$2m$。 自然而然想到 $F(x)$ 会是很多关于 $a_ix$ 的多项式的积，即设： $$A(x)=\sum_{k} \frac{1}{k!} (k+1)^m x^k$$ $$B(x)=\sum_{k} \frac{1}{k!} (k+1)^{2m} x^k$$ 那么有： $$F(x)=\sum_i B(a_ix) \prod_{j\ne i} A(a_j x)$$ $$=\sum_i \frac{B(a_i x)}{A(a_i x)} \prod_i A(a_ix)$$ $$=\sum_i \frac{B(a_i x)}{A(a_i x)} \cdot \exp {\sum_i \ln A(a_ix)}$$ 求出 $\frac{B(x)}{A(x)}$ 和 $\ln A(x)$ 后，需要代入 $a_ix$ 并求和，即第 $t$ 项系数需要乘 $\sum a_i^t$ 于是还要对 $0\le k < n-1$ 预处理一个 $\sum_i a_i^k$。 注意到$\sum_{k\ge 0}a^kx^k=\frac{1}{1-ax}$ 则答案的生成函数为 $$\sum_{i=1}^n\frac{1}{1-a_ix}=\frac{\sum\limits_{i=1}^n\prod\limits_{j\neq i}(1-a_jx)}{\prod\limits_{i=1}^n(1-a_ix)}$$ 其中， $$Q(x)=\prod_{i=1}^n(1-a_ix)$$ 可以用分治 FFT 求出。 对比分子和分母的系数（或是把分母反转，求导，再反转）得到： $$P(x)=\sum_{i=1}^n\prod_{j\neq i}(1-a_jx)=\sum_{k=0}^{n-1}x^k(n-k)[x^k]Q(x)$$