介绍了自然数幂和的几种常见求法.
自然数幂和
定义 $S(n,k)=\sum_{i=0}^{n-1} i^k$ .
拉格朗日插值法
$S(n,k)$ 是一个关于 $n$ 的 $k+1$ 次多项式.
于是可以用拉格朗日插值在 $O(k^2)$ 内求出这个多项式,或者在 $O(k+\log P)$ 内求出某一个 $S(n,k)$ 的值.
计算过程中需要利用逆元,所以要求模数为质数.
第二类斯特林数法
自然数幂的求和不是很直接,但是下降幂求和的形式是十分简单的.
$$
\begin{aligned}
\sum_{i=0}^{n-1} i^{\underline k} &= \frac{1}{k+1}\sum_{i=0}^{n-1}(i+1)^{\underline {k+1}}-i^{\underline {k+1}} \\
&=\frac{n^{\underline {k+1}}}{k+1}
\end{aligned}
$$
于是我们可以考虑用第二类斯特林数将自然数幂展开成下降幂进行求和.
$$
\begin{aligned}
S(n,k)&=\sum_{i=0}^{n-1}i^k \\
&=\sum_{i=0}^{n-1}\sum_{j=0}^k {k\brace j} i^{\underline j} \\
&=\sum_{j=0}^k {k\brace j}\sum_{i=0}^{n-1}i^{\underline j} \\
&=\sum_{j=0}^k {k\brace j} \frac{n^{\underline {j+1}}}{j + 1}
\end{aligned}
$$
若多次询问的 $k$ 不同,我们可以 $O(k^2)$ 预处理第二类斯特林数, 然后 $O(k)$ 回答每个询问.
若多次询问的 $k$ 都相同,根据
$$
{n\brace m} = \frac{1}{m!}\sum_{i=0}^m (-1)^i \binom m i (m-i)^n
$$
可以用 NTT 优化卷积, 以 $O(k\log k)$ 的复杂度求出一行的第二类斯特林数,然后 $O(k)$ 回答每个询问.
若模数不是质数,逆元不一定存在,这个方法仍然可以计算 $S(n,k)$ ,不过复杂度只能做到 $O(k^2)$ .
考虑 $S(n,k)=\sum_{j=0}^k {k\brace j} \frac{n^{\underline {j+1}}}{j + 1}$ ,我们先 $O(k^2)$ 预处理出第二类斯特林数.
计算时, $n^{\underline {j+1}}$ 是 $j+1$ 个连续自然数乘积,其中一定有 $j+1$ 的倍数,找出来后将它除掉 $j+1$ 即可.
如果把剩下的数暴力乘起来,单次询问的时间复杂度仍然为 $O(k^2)$ .
用线段树维护出 $n,n-1,n-2\dots,n-j$ 这个序列的前缀积,后缀积,就可以做到单次询问 $O(k\log k)$ .
伯努利数法
定义伯努利数为对于任意非负整数 $n$ 满足以下等式
$$
[n=0]=\sum_{i=0}^n\binom{n + 1}{i} B_i
$$
的唯一实数列.
可以证明,伯努利数的 EGF 为
$$
B(x)=\sum_{i\ge 0} \frac{B_i}{i!}=\frac{x}{e^x-1}
$$
并且满足
$$
S(n,k)=\frac{1}{k+1}\sum_{i=0}^k \binom{k+1}{i} B_i \cdot n^{k+1-i}
$$
于是可以先用多项式求逆求出前 $k+1$ 个 $B_i$ ,再用 NTT 对于某个固定的 $n$ ,对 $1$ 到 $k$ 内所有的 $i$ 求出 $S(n,i)$ .
一般适用于 $n$ 固定,而 $k$ 的询问有多个的情况,时间复杂度 $O(k\log k)$ .