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)