P7431

· · 题解

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

咋题解全是先通分的 .

首先写出答案的 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) .