关于同时求序列的 $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

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