关于同时求序列的 $0$ 次幂和到 $k$ 次幂和的一些想法

问题

应该是个挺简单的问题

对于 \(k=0,1,\dotsc,m\) 求

\[ f_k=\sum_{i=1}^n a_i^k \]

算法 1

考虑答案的生成函数

\[ f(x)=\sum_{i=0}^\infty f_k x^k \]

一个数 \(a\) 的贡献是

\[ \sum_{i=0}^\infty a^i x^i = \frac{1}{1-ax} \]

因此 \(f(x)=\sum_{i=1}^n \frac{1}{1-a_ix}\)

可以发现

\[ \sum_{i=1}^n \frac{1}{1-a_ix} = \frac{\sum_{i=1}^n \prod_{j\ne i} (1-a_jx)}{\prod_{i=1}^n (1-a_i x)} \]

其中分子的部分可以用分治 NTT 计算，即记录每段的分子分母这两个部分，可以用三次乘法合并

常数比较大

算法 2

继续优化上面的算法

令

\[ \begin{align} g(x)&=\prod_{i=1}^n (1-a_i x) \\ h(x)&=\sum_{i=1}^n \prod_{j\ne i} (1-a_jx) \\ f(x)&=\frac{h(x)}{g(x)} \end{align} \]

可以发现 \(g(x)\) 的 \(i\) 次项系数 \(|g_i|\) 即从 \(a_1,a_2,\dotsc,a_n\) 中选出 \(i\) 个乘积的总和

\(|h_i|\) 即枚举删去一个元素 \(a_j\) 后选出 \(i\) 个乘积的和

一种选出 \(i\) 个的方案在 \(|g_i|\) 中被恰好计算一次，而在 \(|h_i|\) 中被计算 \((n-i)\) 次（只要枚举删掉的那个数不是这 \(i\) 个中的都可以）

于是我们有 \(h_i=(n-i)g_i\)

只需要分治求出 \(g(x)\) 就可以计算 \(h(x)\)，而这个分治每次只需要一次乘法

---

考虑形式化这个求 \(h(x)\) 的过程

可以发现 \(h(x)=g(x)\times n-(g(x))'x\)

因此

\[ \begin{align} f(x)&=\frac{h(x)}{g(x)} \\ &=\frac{g(x)\times n-(g(x))'x}{g(x)} \\ &=n-x\frac{(g(x))'}{g(x)} \end{align} \]

这和之后的算法有一定的联系

算法 3

沿用上面的符号

由 \(\ln(1-ax)=-\sum\limits_{i=1}^\infty \frac{a^i}{i}x^i\)

\[ \begin{align} \ln(g(x))&=\sum_{i=1}^n \ln(\frac{1}{1-a_ix}) \\ &=\sum_{i=1}^n \sum\limits_{j=1}^\infty \frac{a_i^j}{j}x^j \\ &=\sum_{i=1}^\infty \sum_{j=1}^n \frac{a_j^i}{i} x^i \end{align} \]

分治求出 \(g(x)\) 后求 \(\ln(g(x))\)，去掉 \(\frac{1}{i}\) 的系数即可

这其实和算法 2 本质相同

\[ \begin{align} \ln(g(x))&=\int \frac{g'(x)}{g(x)} \end{align} \]

对于这个式子求导相当于去掉了 \(\frac{1}{i}\) 的系数，位移回来后补上常数项，和算法 2 完全相同

算法 4

这里 有，但是我没看懂，反正式子是一样的