自动搬运

查看原文

来自洛谷，原作者为

	jijidawang And in that light, I find deliverance.

搬运于2025-08-24 22:29:49，当前版本为作者最后更新于2023-02-08 18:41:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这就是传说中的数列多幂次求和吗 .

咋题解全是先通分的 .

首先写出答案的 OGF：

$$F(z)=\sum_{k\ge 0}\sum_{i=1}^na_i^kz^k=\sum_{i=1}^n\dfrac1{1-a_iz} $$

然后考虑分治 NTT，每次从中点分治，动态维护答案的分子和分母，合并时暴力通分计算 .

对于 $\dfrac ab+\dfrac cd=\dfrac{ad+bc}{bd}$，可以发现分子分母的次数均被控制在可控范围内，于是可以根据类似一堆一次多项式乘法的分析得到复杂度为 $\Theta(n\log^2n)$ .