数列的多点等幂和

· · 个人记录

前言

尝试优化分治 FFT 时发现的，结果发现早就有人研究过了（这篇文章的标题也是网上找到的），那还是记录一下吧。

本篇博客内容较为低端，建议 dalao 绕路。

介绍

长度为 n 的数列 a_i 的 k 次等幂和定义为 \displaystyle \sum_{i=1}^n {a_i}^k。

下面介绍两种快速求出数列 a_i 的 1 \ldots T 次等幂和的方法，它们的时间复杂度均为 O(n \log^2 n + T \log T)。

方法 1

考虑答案的生成函数

\begin{aligned} F &= \sum_{k=0}^\infty x^k \sum_{i=1}^n {a_i}^k \\ &= \sum_{i=1}^n \sum_{k=0}^\infty (a_ix)^k \\ &= \sum_{i=1}^n {1 \over 1-a_ix} \end{aligned}

不妨设 F = \dfrac P Q，通分后可以得到

\begin{aligned} P &= \sum_{i=1}^n \prod_{j \ne i} (1-a_jx) \\ Q &= \prod_{i=1}^n (1-a_ix) \end{aligned}

利用分治 FFT 可以在 O(n \log^2 n) 时间内计算出 Q。

考虑 P,Q 的组合意义，可以发现 [x^k]P = (n-k)[x^k]Q。

也可以直接根据式子推导：

\begin{aligned} P &= \sum_{i=1}^n \prod_{j \ne i} (1-a_jx) \\ &= \sum_{i=1}^n Q + a_ix \prod_{j \ne i} (1-a_jx) \\ &= nQ - xQ' \end{aligned}

其中利用了乘法的求导法则

\left( \prod_{i=1}^n A_i \right)' = \sum_{i=1}^n {A_i}' \prod_{j \ne i} A_j

比较各项系数可以得到同样的结论。

对 Q 求逆后与 P 卷积即可得到 F。

方法 2

由于

\ln(1-ax) = -\sum_{i=1}^n {(ax)^i \over i}

所以

\begin{aligned} \sum_{i=1}^n {a_i}^k &= -k [x^k] \sum_{i=1}^n \ln(1-a_ix) \\ &= -k [x^k] \ln \prod_{i=1}^n (1-a_ix) \end{aligned}

利用分治 FFT 可以在 O(n \log^2 n) 时间内计算出 \displaystyle \prod_{i=1}^n (1-a_ix)，取对数并提取 1 \ldots T 项系数即可。

如果考虑多项式求对数的实现方式，可以发现这两种方法本质是一样的。

后记

参考资料（同时也是博客标题来源）：快速计算数列 a 的多点等幂和 - Metheus - 知乎