4002 题解

2018-10-21 22:38:47


我来胡一个 $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)$$