Prutekoi's blog

曾经以为具体数学里非整数数列没有什么用，现在真香
伯努利数是可以快速计算自然数幂和的数列。
它这么定义

$\sum_{i=0}^m\binom{m+1}{i}B_i=[m=0]$

移一下项即可得到 $n^2$ 递推。
设

$S_m(n)=\sum_{i=0}^{n-1}i^m$

即为左闭右开的自然数幂和。
则

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

然后就可以实现 $O(m^2)$ 预处理然后 $O(m)$ 求 $S_m(n)$。
所以考虑快速求 $B_i$。
上面的定义式还可以写成这样

$\sum_{i=0}^n\binom{n}{i}B_i=B_n+[n=1]$

发现左边是一个二项卷积，考虑用指数生成函数表示即可化为

$B(z)e^z=B(z)+z$

即

$B(z)=\frac{z}{e^z-1}$

所以直接多项式求逆即可求出 $B_i$。
然后要证一下上面的自然数幂和的公式啦
因为伯努利数有优秀的指数生成函数的表示，所以我们还是考虑生成函数来推。
记 $<S_0(n),S_1(n),S_2(n)...>$ 的指数生成函数为 $S(z,n)$
则

$S(z,n)=\sum_{i\geq0}\sum_{k=0}^{n-1}k^i\frac{z^i}{i!}=\sum_{k=0}^{n-1}e^{kz}=\frac{e^{nz}-1}{e^z-1}$

然后把伯努利数往里代即得

$S(z,n)=B(z)\frac{e^{nz}-1}{z}$

然后把这两个生成函数都展开之后手动卷一卷即可得到上面的公式。

具体数学上还有用归纳法证明的，简直太神仙了，对二项式系数处理得出神入化。有兴趣可以看。

看起来伯努利数被拉格朗日插值吊打了，因为拉格朗日插值不用预处理就可以 $O(m)$ 求点值。不过还是有一点用处的。。？因为拉格朗日插值想求出系数需要快速插值，而用这个只需求一下逆就可以求出系数？