BZOJ2627 伯努利数

这是一道经典的组合数学题目，需要一些基本的组合数学知识。

首先，我们先来了解一下伯努利数。伯努利数是组合数学中的一类数列，它们的递推式如下：

$$B_0 = 1, B_n = -\frac{1}{n+1}\sum_{i=0}^{n-1}{{n+1}\choose{i}}B_i$$

其中 $n\geq 1$，${n\choose k}$ 表示组合数，$B_n$ 表示第 $n$ 个伯努利数。

接下来，我们考虑如何计算 $\sum_{i=0}^{n}{n+1\choose{i}}B_i$。根据二项式定理，我们有：

$$(1+x)^{n+1} = \sum_{i=0}^{n+1}{n+1\choose{i}}x^i$$

对上式两边求导可以得到：

$$(n+1)(1+x)^n = \sum_{i=1}^{n+1}{n+1\choose{i}}ix^{i-1}$$

将 $x=1$ 带入上式，得到：

$$(n+1)\cdot 2^n = \sum_{i=1}^{n+1}{n+1\choose{i}}i$$

注意到 $B_0=1$，我们可以对伯努利数的递推式进行变形：

\begin{aligned} B_n &= -\frac{1}{n+1}\sum_{i=0}^{n-1}{{n+1}\choose{i}}B_i \\ &= -\frac{1}{n+1}\left({{n+1}\choose{0}}B_0 + \sum_{i=1}^{n}{{n+1}\choose{i}}B_i\right) \\ &= -\frac{1}{n+1}\left({{n+1}\choose{0}}B_0 + \sum_{i=1}^{n}{n+1\choose{i}}B_i\right) + \frac{1}{n+1}{{n+1}\choose{0}}B_0 \\ &= -\frac{1}{n+1}\sum_{i=0}^{n}{n+1\choose{i}}B_i + \frac{1}{n+1} \end{aligned}

因此，我们有：

$$\sum_{i=0}^{n}{n+1\choose{i}}B_i = (n+1)(B_{n+1}-1)$$

这个式子可以通过数学归纳法进行证明。

现在，我们已经得到了 $\sum_{i=0}^{n}{n+1\choose{i}}B_i$ 的计算公式，只需要预处理出前 $n$ 个伯努利数就可以在 $O(n)$ 的时间复杂度内解决这个问题了。