【题解】[THUPC2017] 小 L 的计算题 / Sum 生成函数+多项式 loj2409 —Qiuly

这题可以用牛顿多项式做，不过也可以用生成函数搞。

设 $f_i$ 的 $\rm{OGF}$ 为 $\rm{F(x)}$，那么有：
$$\begin{aligned} F(x)&=\sum_{i=0}^{\infty} f_ix^i\\ &=\sum_{i=0}^{\infty} \sum_{k=1}^{n}a_k^ix^i\\ &=\sum_{k=1}^{n}\frac{1}{1-a_kx}\\ &=\sum_{k=1}^{n}1+\frac{a_kx}{1-a_kx}\\ &=n+x\sum_{k=1}^{n}\frac{a_k}{1-a_kx}\\ &=n-x\sum_{k=1}^{n}\frac{-a_k}{1-a_kx}\\ \end{aligned}$$
众所周知：
$$\ln(x)’=\frac{1}{x}\\ \ln(1+x\times y)’=\frac{x}{1+x\times y}\\ \ln(x\times y)=\ln(x)+\ln(y)\\ $$

那么上面的就很显然了：
$$\begin{aligned} F(x)&=n-x\sum_{k=1}^{n}\ln'(1-a_kx)\\ F(x)&=n-x\times \ln(\prod_{k=1}^{n}(1-a_kx))’\\ \end{aligned}$$
分治 $\rm{FFT}$ $+$ 多项式对数函数 $+$ 多项式求导即可。