自然数等幂求和

记 $S_m(n)=\sum_{i=1}^ni^m$，求 $S_m(n)\bmod P$。

$n \le 10^9, m \le 10^3$

拉格朗日插值

把 $1,2,\cdots,m+2$ 插值即可

$$\sum_{i=1}^ni^m=\sum_{i=1}^{m+2}S_m(i)\prod_{j\ne i}\frac{n-j}{i-j}$$

预处理

$$pre_i=\prod_{j=1}^in-j,suf_i=\prod_{j=i}^{m+2}n-j$$

和阶乘逆元。

进一步

$$\sum_{i=1}^ni^m=\sum_{i=1}^{m+2}S_m(i)\frac {pre_{i-1}suf_{i+1}}{(i-1)!(m+2-i)!(-1)^{m+2-i}}$$

直接求 $S_m(1)\sim S_m(m+2)$ 是 $O(m\log m)$ 的，注意 $i^m$ 是完全积性函数，可以只对质数使用快速幂，其他的用欧拉筛推出来，复杂度 $O(m)$。

第二类斯特林数

$$\sum_{i=0}^ni^m=\sum_{i=1}^m{m \brace i}\frac 1{i+1}(n+1)^{\underline{i+1}}$$

预处理

$$\begin{aligned} {0 \brace 0} &= 1 \\ {n \brace m} &= {n - 1 \brace m - 1} + m{n - 1 \brace m} \end{aligned}$$

复杂度 $O(m^2)$，好处是可以不用求逆元，在 $P$ 不是质数时也管用。

伯努利数

$$\sum_{i=1}^ni^m=\frac 1{m+1}\sum_{i=0}^m\binom{m+1}iB_i(n+1)^{m+1-i}$$

其中 $B_n$ 表示 第一伯努利数。

预处理

$$\begin{aligned} B_0=1\\ \sum_{i=0}^m\binom{m+1}iB_i=0 \end{aligned}$$

$O(m^2)$ 预处理完后可以 $O(m)$ 询问。

伯努利数更强大的功能是 $O(m\log m)$ 对所有 $1\sim m$ 都计算出答案。

伯努利数的指数型生成函数

$$\sum_{k=0}^{\infty}B_k\frac{x^k}{k!}=\frac x{e^x-1}$$

通过多项式求逆可以得到伯努利数，再通过卷积可以对所有 $1\sim m$ 都计算出答案。