伯努利数

定义&求解

设数列 \(B_{n}\) 为伯努利数,满足一下性质:

\[\begin{aligned} B_{0}&=1\\sum^{n}_{i=0}\binom{n+1}{i}B_{i}&=0\\end{aligned} \]

在 OI 中一般用这个来求 \(k\) 次方前缀和。

显然有一个 \(O(n^2)\) 的递推式:

\[\begin{aligned} \binom{n+1}{n}B_{n}&=-\sum^{n-1}_{i=0}\binom{n+1}{i}B_{i}\B_{n}&=\frac{-\sum^{n-1}_{i=0}\binom{n+1}{i}B_{i}}{n+1} \end{aligned} \]

实际上,可以利用生成函数来做到 \(O(n\log n)\)

\[\begin{aligned} \sum^{n-1}_{i=0}\binom{n}{i}B_{i}&=0\\sum^{n}_{i=0}\binom{n}{i}B_{i}&=B_{n}\\sum^{n}_{i=0}\frac{n!}{i!(n-i)!}B_{i}&=B_{n}\\sum^{n}_{i=0}\frac{B_{i}}{i!(n-i)!}&=\frac{B_{n}}{n!}\\end{aligned} \]

如果我们令 \(B(x)\) 为其指数生成函数,那么可以发现左边实际上是卷上了一个 \(e^x\)

但是上面这个式子只当 \(n>1\) 的时候才成立,所以要手动修正 \(B_{0},B_{1}\) 的系数。

\[\begin{aligned} B(x)&=e^xB(x)-x\B(x)&=\frac{x}{e^x-1}\\end{aligned} \]

直接套上一个多项式求逆就可以 \(O(n\log n)\) 的复杂度求出 \(B\) 了。

简单应用

\(S_{k}(n)=\sum^{n}_{i=1}i^k\)

我们令 \(F(x)\)\(S(n)\) 的指数生成函数。

\[\begin{aligned} F(x)&=\sum^{+\infty}_{i=0}\frac{x^iS_{i}(n)}{i!}\&=\sum^{+\infty}_{i=0}\frac{x^i\sum^{n}_{j=1}j^i}{i!}\&=\sum^{n}_{j=0}\sum^{+\infty}_{i=0}\frac{x^ij^i}{i!}\&=\sum^{n}_{j=1}e^{ix}\&=\frac{e^{(n+1)x}-e^x}{e^x-1}\&=\frac{B(x)e^x}{x}(e^{nx}-1)\&=\frac{B(x)e^x}{x}(-1+\sum^{+\infty}_{i=0}\frac{n^ix^i}{i!})\&=\frac{B(x)+x}{x}(-1+\sum^{+\infty}_{i=0}\frac{n^ix^i}{i!})\\end{aligned} \]

为了方便,我们定义 \(B‘(x)=B(x)+x\)

\[\begin{aligned} &\frac{B‘(x)}{x}(-1+\sum^{+\infty}_{i=0}\frac{n^ix^i}{i!})\&=B‘(x)\sum^{+\infty}_{i=0}\frac{n^{i+1}x^i}{(i+1)!}\\end{aligned} \]

对于只要求第 \(k\) 项的时候,可以暴力卷积。

\[\begin{aligned} S_{k}(n)&=\sum^{k}_{i=0}\frac{B‘_{i}n^{k-i+1}}{(k-i+1)!i!}\&=\frac{1}{(k+1)!}\sum^{k}_{i=0}\binom{k+1}{i}B‘_{i}n^{k-i+1}\\ \end{aligned} \]

至此,可以做到 \(O(k)\) 求出单项的值。 虽然有不用脑子,且复杂度差不多的插值法

伯努利数

上一篇:一文看懂支付宝金融智能背后的 AI 技术


下一篇:你的旅途才刚刚开始