【题解】[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} $ $+$ 多项式对数函数 $+$ 多项式求导即可。