容易想到直接枚举树

$$ \sum_T\left(\prod_{i=1}^na_i^{d_i}d_i^m\right)\left(\sum_{i=1}^nd_i^m\right) $$

$$ \sum_T\sum_{i=1}^n a_i^{d_i}d_i^{2m}\prod_{j\neq i}a_j^{d_j}d_j^m $$

运用 $\mathrm{Prufer}$ 序列这一工具

$$ \sum_{i=1}^n\sum_{\sum k_j=n-2}\frac{(n-2)!}{\prod k_j!}a_i^{k_i+1}(k_i+1)^{2m}\prod_{j\neq i}(a_j^{k_j+1}(k_j+1)^m) $$

$$ (n-2)!\left(\prod_{j=1}^n a_j\right)\sum_{i=1}^n\sum_{\sum k_j=n-2}\frac{a_i^{k_i}(k_i+1)^{2m}}{k_i!}\prod_{j\neq i}\frac{a_j^{k_j}(k_j+1)^m}{k_j!} $$

设

$$ \begin{aligned} \left[{z^n}\right]F_i(z)&=\frac{a_i^n(n+1)^{2m}}{n!} \\
\left[{z^n}\right]G_i(z)&=\frac{a_i^n(n+1)^m}{n!} \end{aligned} $$

将非常数项写成卷积形式

$$ \left[{z^{n-2}}\right]\sum_{i=1}^n\frac{F_i(z)}{G_i(z)}\left(\prod_{i=1}^nG_i(z)\right) $$

问题变为快速求解这个卷积。设

$$ F(z)=\sum_{n=0} \frac{(n+1)^{2m}}{n!}z^n,G(z)=\sum_{n=0}\frac{(n+1)^m}{n!}z^n $$

则有

$$ F_i(z)=F(a_iz),G_i(z)=G(a_iz) $$

现在需要考虑对于任意

$$ H_i(z)=\sum_{n=0}a_i^nh_nz^n=\frac{1}{1-a_iz} $$

求解

$$ \begin{aligned} \sum_{i=1}^n H_i(z)=\sum_{i=1}^n\frac{1}{1-a_iz} \end{aligned} $$

因为连乘项是 $H_i(z)=\ln G(a_iz)$ 并且 $\exp$ 回原式，而连加项其实是 $H_i(z)=\frac{F(a_iz)}{G(a_iz)}$。对于这两部分都只需要求一遍 $\ln G(z)$ 和 $\frac{F(z)}{G(z)}$。

设

$$ u=\prod_{i=1}^n (1-a_iz) $$

则所求变为

$$ \frac{u'}{u} $$

使用分治 $\mathrm{NTT}$ 求出 $u$ 的值即可，时间复杂度为 $O(n \log^2 n)$

最后修改于 2021-08-08