经过一天的学习，我们发现伯努利数是个非常有用 （个屁） 的数列
定义
但是...伯努利数是什么呢？我们先给伯努利数一个定义：
令 \(B(i)\) 表示 伯努利数第 i 项，那么有：
\[\sum_{i=0}^{n} \begin{pmatrix} n+1\\i \end{pmatrix} B_i=0 ,~~ n>0\]
当然 \(B_0=1\) ，于是上面的式子就可以一直推下去了...
暴力计算
我们按照上面的式子可以算出：
\[B_0=1,B_1=-{1\over2},B_2={1\over 6},B_3={0},B4={1\over 30}······\]
但是这样的效率嘛 【滑稽
当然是 \(n^2\) 的啦~ 于是我们试图寻找更高效的办法...
高效计算
我们发现，根据定义有这么个等式：
\[\sum_{i=0}^{n}\begin{pmatrix} n\\i \end{pmatrix} B_i = B_n ,n>1\]
这里原本 n 是 n+1 的，为了方便我们把 n 带进去...
然后这个式子有什么用呢？当然有用咯~ 这玩意儿可是能化成卷积的形式丫！
于是拆个组合数玩玩，看这里：
\[\sum_{i=0}^{n}{ B_i\over i!(n-i)!} = {B_n\over n!} ,n>1\]
我们发现 \(n=0\) 时，其实也满足上面的式子，只要我们定义 \(0!=1\)
\[\sum_{i=0}^{n}{ B_i\over i!} {1\over (n-i)!} = {B_n\over n!} ,n\neq1\]
\[\sum_{n=0,n\neq1}^{\infty}\sum_{i=0}^{n}{ B_i\over i!}~ · {1\over (n-i)!} = \sum_{n=0,n\neq1}^\infty {B_n\over n!} \]
注意上面的 n 仍然不等于 1 ...
然后我们是不是发现这玩意儿左边其实是...卷积呢！\(1\over i!\) 不就是每项系数为 1 的多项式指数函数？
我们把伯努利数除去阶乘当做是一个多项式的系数，那么原来的式子就可以搞生成函数了！
但我们首先还要把 n=1 的情况加进去：
\[\sum_{n=0,n\neq1}^{\infty}\sum_{i=0}^{n}{ B_i\over i!}~ · {1\over (n-i)!} = \sum_{n=0,n\neq1}^\infty {B_n\over n!} \]
\[\sum_{n=0}^{\infty}\sum_{i=0}^{n}{ B_i\over i!}~ · {1\over (n-i)!} = \sum_{n=0}^\infty {B_n\over n!} +[n=1] \]
你问我为什么这么写？暴力算一下 n=1 的情况不就发现两边差了多少嘛！
然后转个多项式我们就可以开始生成函数了 QVQ
\[\sum_{n=0}^{\infty}\Big(\sum_{i=0}^{n}{ B_i\over i!}~ · {1\over (n-i)!}\Big) x^n = \sum_{n=0}^\infty \Big( {B_n\over n!} +[n=1] \Big) x^n\]
\[\sum_{n=0}^{\infty} \sum_{i=0}^{n}{ B_i\over i!}x^i~ · {1\over (n-i)!} x^{n-i} = \sum_{n=0}^\infty \Big( {B_n\over n!} +[n=1] \Big) x^n\]
\[B(x)e^x=B(x) +x\]
这里之所以加了 x 是因为上面的 \(x^1\) 系数多了个 1
然后我们继续推式子：
\[B(x)={x\over e^x-1}\]
\[B(x)=({e^x-1\over x})'\]
也就是说，我们只要阶乘算出来整体左移一位然后求个逆就好了
code
代码如下...
坑
模板
然后这里是板子题：
应用
伯努利数有个非常良好 （个屁） 的性质：
令：
\[S(n,k)=\sum_{i=1}^{n-1} i^k\]
则：
\[S(n,k)={1\over k+1} \sum_{i=0}^k \begin{pmatrix} k+1 \\ i \end{pmatrix} B_i n^{k+1-i} \]
即：
\[\sum_{i=1}^{n-1} i^k={1\over k+1} \sum_{i=0}^k \begin{pmatrix} k+1 \\ i \end{pmatrix} B_i n^{k+1-i}\]
PS：关于上面等式的证明可以看这里
然后一系列推倒：
\[{1\over k+1} \sum_{i=1}^{k+1} \begin{pmatrix} k+1 \\ k+1-i \end{pmatrix} B_{k+1-i} n^i\]
\[k! \sum_{i=1}^{k+1} {B_{k+1-i}\over (k+1-i)!} {n^i\over i!}\]
这可不就是卷积的形式嘛！
然后我们发现现在可以在一些 (dl)数学题里面大展拳脚了呢~
比如这道：