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

设 $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} $ $+$ 多项式对数函数 $+$ 多项式求导即可。

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注