求自然数幂和的若干方法
lhm_
·
·
个人记录
可能是更好的阅读体验
形如 S_k(n)=\sum\limits_{i=0}^n i^k 的式子被称为自然数幂和。
本文介绍了求自然数幂和的若干方法，其中包括斯特林数和伯努利数的一些应用，其中证明的推导过程也有一些推式子的技巧。
扰动法
应用两次扰动法，当 k \geqslant 1 时，得：
\large\begin{aligned}
S_k(n)&=\sum_{i=0}^ni^k \\
&=\sum_{i=0}^n(i+1)^k-(n+1)^k \\
&=\sum_{i=0}^n\sum_{j=0}^k\binom{k}{j}i^j-(n+1)^k \\
&=\sum_{j=0}^k\binom{k}{j}S_j(n)-(n+1)^k \\
&=\sum_{j=0}^{k-2}\binom{k}{j}S_j(n)+kS_{k-1}(n)+S_k(n)-(n+1)^k \\
\end{aligned}
得：
\large\begin{aligned}
S_{k-1}(n)&=\frac{(n+1)^k-\sum\limits_{j=0}^{k-2}\binom{k}{j}S_j(n)}{k} \\
S_k(n)&=\frac{(n+1)^{k+1}-\sum\limits_{j=0}^{k-1}\binom{k+1}{j}S_j(n)}{k+1} \\
\end{aligned}
直接计算可以做到 O(k^2)。分治 FFT 可以做到 O(k \log^2 k)。
拉格朗日插值法
由扰动法推得的式子，发现 S_k(n) 为 k+1 次多项式，因此可以考虑拉格朗日插值法，代入 (0,S_k(0)),(1,S_k(1)),\dots,(k+1,S_k(k+1)) 这 k+2 个点值，得：
\large\begin{aligned}
f(x) &= \sum_{i = 0}^{k+1} y_i \prod_{i \not = j} \frac{x - x_j}{x_i - x_j} \\
S_k(n) &= \sum_{i = 0}^{k+1} S_k(i) \prod_{i \not = j} \frac{n - j}{i - j} \\
\end{aligned}
因为取值是连续的，后一项中的分子和分母可以分别计算，预处理后可以实现复杂度为 O(k)。
考虑如何计算 S_k(i)，对于 i^k 可以进行线性筛，每个素数暴力快速幂，因为小于等于 n 的素数个数约为 \frac{n}{\ln n}，得复杂度为 O(\frac{k}{\ln k}\log k)=O(k)。
因此总复杂度为 O(k)。
例题：The Sum of the k-th Powers
第一类斯特林数
\large x^{\overline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i
通过组合意义即可证明，其也可以用归纳法证明：
已知：
\large x^{\overline{n-1}}=\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\ i\end{bmatrix}x^i
得：
\large\begin{aligned}
x^{\overline{n-1}}&=\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\ i\end{bmatrix}x^i \\
(x+n-1)x^{\overline{n-1}}&=(x+n-1)\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\ i\end{bmatrix}x^i \\
x^{\overline{n}}&=(n-1)\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\ i\end{bmatrix}x^i+\sum_{i=1}^{n}\begin{bmatrix}n-1\\ i-1\end{bmatrix}x^i \\
x^{\overline{n}}&=\sum_{i=0}^{n}\begin{bmatrix}n\\ i\end{bmatrix}x^i \\
\end{aligned}
代入得：
\large\begin{aligned}
S_k(n)&=\sum_{i=0}^ni^k \\
&=\sum_{i=0}^n(i^{\overline{k}}-\sum_{j=0}^{k-1}\begin{bmatrix}k\\ j\end{bmatrix}i^j) \\
&=\sum_{i=0}^ni^{\overline{k}}-\sum_{i=0}^n\sum_{j=0}^{k-1}\begin{bmatrix}k\\ j\end{bmatrix}i^j \\
&=\sum_{i=0}^n\binom{i+k-1}{k}k!-\sum_{j=0}^{k-1}\begin{bmatrix}k\\ j\end{bmatrix}S_j(n) \\
&=\binom{n+k}{k+1}k!-\sum_{j=0}^{k-1}\begin{bmatrix}k\\ j\end{bmatrix}S_j(n) \\
&=\frac{(n+k)!}{(n-1)!(k+1)!}k!-\sum_{j=0}^{k-1}\begin{bmatrix}k\\ j\end{bmatrix}S_j(n) \\
&=\frac{n^{\overline{k+1}}}{k+1}-\sum_{j=0}^{k-1}\begin{bmatrix}k\\ j\end{bmatrix}S_j(n) \\
\end{aligned}
直接计算可以做到 O(k^2)。不用保证模数存在逆元，k+1 一定是 n^{\overline{k+1}} 的约数。
应用归纳法可得：
\large x^{\overline{n}} = (-1)^n(-x)^{\underline{n}} \\
\large x^{\underline{n}} = (-1)^n(-x)^{\overline{n}} \\
考虑对于 x^{\overline{n}} = (-1)^n(-x)^{\underline{n}}，将其中 x 换为 -x，得：
\large (-x)^{\overline{n}} = (-1)^nx^{\underline{n}}
因为有 x^{\overline{n}}=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i，得：
\large\begin{aligned}
(-1)^nx^{\underline{n}} &= \sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}(-x)^i \\
x^{\underline{n}} &= \sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\ i\end{bmatrix}x^i \\
\end{aligned}
应用这个式子也可以进行求解：
\large\begin{aligned}
S_k(n)&=\sum_{i=0}^ni^k \\
&=\sum_{i=0}^n(i^{\underline{k}}-\sum_{j=0}^{k-1}(-1)^{k-j}\begin{bmatrix}k\\ j\end{bmatrix}i^j) \\
&=\sum_{i=0}^ni^{\underline{k}}-\sum_{i=0}^n\sum_{j=0}^{k-1}(-1)^{k-j}\begin{bmatrix}k\\ j\end{bmatrix}i^j \\
&=\sum_{i=0}^n\binom{i}{k}k!-\sum_{j=0}^{k-1}(-1)^{k-j}\begin{bmatrix}k\\ j\end{bmatrix}S_j(n) \\
&=\binom{n+1}{k+1}k!-\sum_{j=0}^{k-1}(-1)^{k-j}\begin{bmatrix}k\\ j\end{bmatrix}S_j(n) \\
&=\frac{(n+1)^{\underline{k+1}}}{k+1}-\sum_{j=0}^{k-1}(-1)^{k-j}\begin{bmatrix}k\\ j\end{bmatrix}S_j(n) \\
\end{aligned}
直接计算可以做到 O(k^2)。不用保证模数存在逆元，k+1 一定是 (n+1)^{\underline{k+1}} 的约数。
第二类斯特林数
\large x^n = \sum_{i=0}^n \begin{Bmatrix} n \\i \end{Bmatrix} x^{\underline{i}}
通过组合意义即可证明，其也可以用归纳法证明：
已知：
\large x^{n-1} = \sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} x^{\underline{i}}
得：
\large\begin{aligned}
\large x^{n-1} &= \sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} x^{\underline{i}} \\
\large x^n &= x\sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} x^{\underline{i}} \\
\large x^n &= \sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} ix^{\underline{i}} +\sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} (x-i)x^{\underline{i}} \\
\large x^n &= \sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} ix^{\underline{i}} +\sum_{i=1}^n \begin{Bmatrix} n-1 \\i-1 \end{Bmatrix} x^{\underline{i}} \\
\large x^n &= \sum_{i=0}^n \begin{Bmatrix} n \\i \end{Bmatrix} x^{\underline{i}} \\
\end{aligned}
代入得：
\large\begin{aligned}
S_k(n)&=\sum_{i=0}^ni^k \\
&=\sum_{i=0}^n\sum_{j=0}^k\begin{Bmatrix} k \\j \end{Bmatrix} i^{\underline{j}} \\
&=\sum_{j=0}^k\begin{Bmatrix} k \\j \end{Bmatrix}\sum_{i=0}^n i^{\underline{j}} \\
&=\sum_{j=0}^k\begin{Bmatrix} k \\j \end{Bmatrix}\sum_{i=0}^n \binom{i}{j}j! \\
&=\sum_{j=0}^k\begin{Bmatrix} k \\j \end{Bmatrix} \binom{n+1}{j+1}j! \\
&=\sum_{j=0}^k\begin{Bmatrix} k \\j \end{Bmatrix} \frac{(n+1)^{\underline{j+1}}}{j+1} \\
\end{aligned}
直接计算可以做到 O(k^2)。不用保证模数存在逆元，j+1 一定是 (n+1)^{\underline{j+1}} 的约数。可以通过卷积 O(n \log n) 求出第二类斯特林数一行后快速求解。
伯努利数
伯努利数前几项为 1,-\frac{1}{2},\frac{1}{6},0,-\frac{1}{30}，其为非整数数列，其定义为：
\large \sum_{i=0}^{n}\binom{n+1}{i}B_i=[n=0]
可以进行 O(n^2) 递推求伯努利数。还可以通过生成函数快速求伯努利数，得：
\large\begin{aligned}
\sum_{i=0}^{n}\binom{n+1}{i}B_i&=[n=0] \\
\sum_{i=0}^{n+1}\binom{n+1}{i}B_i&=B_{n+1}+[n=0] \\
\sum_{i=0}^{n}\binom{n}{i}B_i&=B_{n}+[n=1] \\
\end{aligned}
发现左边为伯努利数的指数生成函数和指数生成函数 e^x 的卷积，得：
\large\begin{aligned}
B(x)e^x &= B(x) + x \\
B(x) &= \frac{x}{e^x-1} \\
\end{aligned}
可以多项式求逆实现 O(n \log n) 求伯努利数。
这里设 S_k(n)=\sum\limits_{i=0}^{n-1}i^k，伯努利数为自然数幂和对应的多项式的系数：
\large S_k(n)=\frac{1}{k+1}\sum_{i=0}^k\binom{k+1}{i}B_in^{k+1-i}
考虑证明，设 F(x) 为 S_k(n) 的生成函数，得：
\large\begin{aligned}
F(x) &= \sum_{i \geqslant 0} \frac{S_i(n)}{i!}x^i \\
&= \sum_{i \geqslant 0}\sum_{j=0}^{n-1} j^i \frac{x^i}{i!} \\
&= \sum_{j=0}^{n-1}\sum_{i \geqslant 0} \frac{(jx)^i}{i!} \\
&= \sum_{j=0}^{n-1}e^{jx} \\
&= \frac{e^{nx}-1}{e^x-1} \\
&= B(x)\frac{e^{nx}-1}{x} \\
&= B(x)\frac{\sum\limits_{i \geqslant 1} \frac{(nx)^i}{i!}}{x} \\
&= B(x) \sum_{i \geqslant 0} \frac{n^{i+1}x^i}{(i+1)!}\\
\end{aligned}
因为 \left [x^k\right ]F(x)=\frac{S_k(n)}{k!}，得：
\large\begin{aligned}
S_k(n) &= k!\sum_{i = 0}^k \frac{B_in^{k+1-i}}{i!(k+1-i)!} \\
S_k(n) &= \frac{1}{k+1}\sum_{i=0}^k\binom{k+1}{i}B_in^{k+1-i} \\
\end{aligned}
应用伯努利数可以求出自然数幂和对应的多项式的系数。