伯努利数相关

发表于 2024-03-27 更新于 2024-04-22 本文字数： 4.7k 阅读时长 ≈ 4 分钟

求等幂和

S_k(n)=\sum_{i=0}^{n-1} i^k,(n\le 10^9,k\le 2000)

虽然这个题之前已经有很多优秀的 $\mathcal O(k)$ 做法，比如拉格朗日插值，以及转下降幂之后有限微积分，但是只针对这个问题，伯努利数的做法适用性更强。

首先由于等幂和的差分是 $k$ 次多项式，所以等幂和是 $k+1$ 次多项式，即：

S_k(n)=\sum_{i=0}^{k+1} a_in^i

由于要寻找 $S_k(n)$ 与 $n$ 的低次幂之间的关系，因此设生成函数：

F_n(x)=\sum_{i=0} S_i(n)x^i\\ =\sum_{j=0}^{n-1} \sum_{i=0} (jx)^i=\sum_{j=0}^{n-1} \frac{1}{1-jx}

然后，就寄了，因为这个加法毫无做法。

此时容易发现 $\frac{1}{1-x}$ 对应着指数生成函数中的 $e^x$ ，而 $e^x$ 的加法可以等比数列，因此：

\hat F(x)=\sum_{i=0} S_i(n)\frac{x^i}{i!}\\ =\sum_{j=0}^{n-1} e^{jx}=\frac{1-e^{nx}}{1-e^x}

分子形式简单，直接去展开 $\frac{1}{1-e^x}$ ，分母常数项是 $0$ 不太好，因此改成 $\frac{x}{1-e^x}$ ：

\frac{x}{1-e^x}=x\sum_{i=0} e^{ix}\\ [x^{k+1}]\sum_{i=0} e^{ix}=\sum_{i=0} \frac{i^k}{k!}=\frac{\zeta(-k)}{k!}

发现爆了，想了好久，结果是第一步有问题 /qd。

考虑一下这个等比数列，等比数列区间求和是没问题的，关键是现在是无限项求和，是什么给了我们这样这样展开的依据呢？

\frac{1}{1-x}=\sum_{i=0} x^i

这个是对的，把无限项求和的上界些出来试试？

\lim_{N\to \infty} \sum_{i=0}^N x^i = \frac{1-x^{N+1}}{1-x}

注意到此时我们保留前若干项的时候， $x^{N+1}$ 这一项不会产生影响，也就是在原来的无限序列上把最后的 $x^N$ 删掉是无影响的，因此可以去掉，保证了正确性。

但是在 $e^{xi}$ 这里，最后的 $e^{Nx}$ 会对前面的 $[x^k]$ 产生 $-N^k$ 的贡献，因此无法删掉，所以上面第一步是错误的。

说回正题，那怎么求出 $[x^k]\dfrac{x}{1-e^x}$ 呢？

考虑去推递推关系，令：

\frac{x}{1-e^x}=\sum_{i=0} \frac{b_ix^i}{i!}\\ x=\hat B-e^x\hat B\\ [k=1]=\frac{b_k}{k!}-\sum_{i=0}^k \frac{1}{i!}\frac{b_{k-i}}{(k-i)!}\\

此时其实就已经可以递推了，但还是推一下更优美的形式：

[k=1]k!=b_k-\sum_{i=0}^n \binom{k}{i}b_{i}\\ \sum_{i=0}^n \binom{n+1}{i}b_j=[n=0]

此时 $b$ 数列叫做伯努利数。

回到最前面：

\hat F(x)=\sum_{i=0} S_i(n)\frac{x^i}{i!}=\frac{1-e^{nx}}{1-e^x}\\ =\frac{x}{1-e^x}\frac{1-e^{nx}}{x}\\ [x^k]\frac{1-e^{nx}}{x}=\frac{n^{k+1}}{(k+1)!}(k\ge 0)

S_m(n)=[\frac{x^m}{m!}]\hat F_m(x)=\sum_{i=0}^m \frac{m!}{i!(m-i+1)!}b_in^{m-i+1}\\ =\frac{1}{m+1}\sum_{i=0}^m \binom{m+1}{i}b_in^{m-i+1}

因此在 $\mathcal O(k^2)$ 的预处理之后，可以 $\mathcal O(k)$ 求出一个 $k$ 的等幂和的系数。

小技巧：如果题目要找 $S_m(n+1)$ 的系数咋办？

弱智（我）的做法，直接二项式展开，但是这样单次给出系数就变成 $\mathcal O(k^2)$ 了，非常不牛。

实际上，只需要考虑加上一个 $n^m$ ，观察式子，容易发现把 $b_1$ 加一即可。

给个例题。

扩展一下上面的东西，求一下下面这个：

A(x)=\sum_{i=0}^n a_ix^i\\ S(A)=\sum_{i=0}^n a_ii^k

先观察一下上面的等幂和，把关键式子写出来：

A(x)=\sum_{i=0}^n x^i=\frac{1-x^n}{1-x}\\ \hat F(x)=\frac{1-e^{nx}}{1-e^x}\\ S(A)=[\frac{x^k}{k!}]\hat F(x)

这提示我们把 $x$ 换成 $e^x$ 来得到其指数生成函数，下面证明一下：

A(x)=\sum_{i=0}^n a_ix^i\\ \hat F(x)=\sum_{i=0}^n a_ie^{xi}\\ [\frac{x^k}{k!}]\hat F(x)=\sum_{i=0}^n a_ii^k

已知长度为 $n$ 等差数列 $a_i=A+Bi$ ，求 $\sum_{i=0}^{n-1} a_i^k$

A(x)=x^A(\frac{1-x^{nB}}{1-x^B})\\ \hat F(x)=e^{Ax}(\frac{1-e^{nBx}}{1-e^{Bx}})\\ \frac{x}{1-e^x}=\sum_{i=0} \frac{b_ix^i}{i!}\\ \frac{x}{1-e^{Bx}}=\sum_{i=0}\frac{b_iB^ix^i}{i!}\\ S(A)=[\frac{x^k}{k!}]=\frac{1}{k+1}\sum_{i=0}^k \binom{k+1}{i}b_iB^i(a_n^{k-i+1}-a_0^{k-i+1})

已知两个数 $A,B$ ，保证 $\gcd(A,B)=1$ ，求所有无法用 $s=Ax+By(x,y\ge 0)$ 表示的 $s$ 的 $k$ 次方和。

$A,B\le 10^{18},k\le 10^5$ 。

考虑 $A,B$ 表出数的条件，如果只是满足 $x\ge 0,y\ge 0$ ，这样会算重，因此强制让 $B>x\ge 0$ ，这样一个能表出的数的表示方法就唯一了。

写出生成函数：

A(x)=\frac{1}{x^d-1}-\frac{1-x^{AB}}{(1-x^A)(1-x^B)}\\ \hat F(x)=\frac{1}{e^{x}-1}-\frac{1-e^{ABx}}{(1-e^{Ax})(1-e^{Bx})}

和上面做法一样，把 $\dfrac{1}{e^{Ax}-1}$ 用伯努利数展开，然后卷积一下就行。

复杂度 $O(k\log k)$ 。