求自然数幂和

简述求自然数幂和$s(n,k)=\sum_{i=1}^{n}i^k$的几种方法：

1、矩阵快速幂

当$i>1$时，$i^k=(i-1+1)^k=\sum_{j=0}^kC_k^j(i-1)^j$

所以可以这样：

$$\begin{align*} s(n,k)&=\sum_{i=1}^{n}i^k\\ &=\left(\sum_{i=2}^{n}\sum_{j=0}^kC_k^j(i-1)^j\right)+1\\ &=\left(\sum_{j=0}^kC_k^j\sum_{i=2}^n(i-1)^j\right)+1\\ &=\left(\sum_{j=0}^kC_k^js(n-1,j)\right)+1 \end{align*}$$

这里可以用矩阵快速幂处理，时间复杂度$O(k^3logn).$

2、差分推公式

$$(i+1)^{k+1}-i^{k+1}=\sum_{j=0}^{k}C_{k+1}^ji^j$$
把$i=1,2,...,n$的式子加起来得到:
$$\begin{align*} (n+1)^{k+1}-1 &= \sum_{i=1}^{n}\sum_{j=0}^{k}C_{k+1}^ji^j\\ &= \sum_{j=0}^{k}C_{k+1}^j\sum_{i=1}^{n}i^j\\ &= \sum_{j=0}^kC_{k+1}^js(n,j) \end{align*}$$
使用$DP$可以在时间复杂度$O(k^2)$内求解.

3、伯努利数

$$\begin{align*} s(n,k)=\frac{1}{k+1}\sum_{i=1}^{k+1}C_{k+1}^iB_{k+1-i}(n+1)^i \end{align*}$$
其中$B_i$表示伯努利数，$B_0=1$，当$n>0$可以通过下列公式计算：
$$\begin{align*} \sum_{i=0}^nC_{n+1}^iB_i=0 \end{align*}$$
朴素计算可以在$O(k^2)$时间内算出伯努利数前k项，然后通过$O(k)$的时间复杂度计算$s(n,k)$.
$PS.$注意特判$k=0$的情况,$0^0=1$,需要注意要求解的是$\sum_{i=0}^ni^k$还是$\sum_{i=1}^ni^k$,只有当$k=0$的情况下两个式子的结果不一样.

另一种计算伯努利数的方法是母函数法：

$$\begin{align*} f(x)&=\sum_{i=0}^{\infty}{\frac{B_i}{i!}x^i}\\ &=\frac{x}{e^x-1}\\ &=\frac{x}{\sum_{i=1}^{\infty}\frac{x^i}{i!}}\\ &=\frac{1}{\sum_{i=0}^{\infty}\frac{x^i}{(i+1)!}} \end{align*}$$
用$FFT$求多项式逆，可以在$O(nlog^2n)$的时间内求出前$n$项.

4、拉格朗日插值

通过以上的公式推导显然可知$s(n,k)$是和$n$有关的$k+1$次多项式.即：

$$\begin{align*} s(n,k)=\sum_{i=0}^{k+1}A_in^i \end{align*}$$
显然对同一个$k$来说，$A_i$是一样的，那么直接使用拉格朗日插值法求出$A_i$即可.

下面介绍一下拉格朗日插值法：
对于给定的$n$个点$\{(x_0,y_0),(x_1,y_1),...,(x_{n-1},y_{n-1})\}$,可以唯一确定一个$n-1$次多项式函数$f(x)=\sum_{i=0}^{n-1}A_ix^i$经过这$n$个点.
拉格朗日插值法的结论是：

$$\begin{align*} f(x)=\sum_{i=0}^{n-1}y_i\prod_{j=0,j\neq i}^{n-1}\frac{x-x_j}{x_i-x_j} \end{align*}$$
此式子显然可以证明通过$\{(x_0,y_0),(x_1,y_1),...,(x_{n-1},y_{n-1})\}$这$n$个点.
在此题下要求解$s(n,k)$无需把$A_i$给求出，根据插值法的式子$f(x)$就可以通过预处理在$O(klogk)$的时间把$s(n,k)$求出.