当前位置：首页 > 学习教程 > 编程语言

伯努利数,求解自然数幂和的关键系数

2020/10/8 20:27:52 文章标签:

正题我们来考虑这个东西如何用与k相关的时间快速计算. 我们记我们构造其关于k的EGF,则有: 可以发现这是一个等比数列求和的形式,那么就有: 接着,我们将其表示为拆成两部分可以观察到,后面的那一部分,相当于因为EGF自带一个i!的系数,这个EGF十分有规律,可以求而前边一部分貌…

正题

我们来考虑 $\sum_{i=0}^n i^k$ 这个东西如何用与k相关的时间快速计算.

我们记 $S(n,k)=\sum_{i=0}^n i^k$

我们构造其关于k的EGF,则有:

$\\G_n(x)=\sum_{k=0}\sum_{i=0}^n i^k\frac{x^k}{k!} \\=\sum_{i=0}^n\sum_k i^k\frac{x^k}{k!} \\=\sum_{i=0}^n e^{xi}$

可以发现这是一个等比数列求和的形式,那么就有:

$(e^x-1)G_n(x)=e^{(n+1)x}-1 \to G_n(x)=\frac{e^{(n+1)x}-1}{e^x-1}$

接着,我们将其表示为拆成两部分 $G_n(x)=\frac{x}{e^x-1}*\frac{e^{(n+1)x}-1}{x}$

可以观察到,后面的那一部分,相当于 $EGF\left \{ \frac{n+1}{1} ,\frac{(n+1)^2}{2},\frac{(n+1)^3}{3},... \right \}$

因为EGF自带一个i!的系数,这个EGF十分有规律,可以 $O(k)$ 求

而前边一部分貌似就没那么有规律了,我们将它们设为 $EGF\left \{ B_0,B_1,... \right \}$

而这个序列B就被称为伯努利数.

同时,因为是EGF卷积的形式,我们可以将它们通过式子写出来:

$\\\frac{S(n,k)}{k!}=\sum_{i=0}^k\frac{B_i}{i!}\frac{(n+1)^{k-i+1}}{(k-i+1)!} \\S(n,k)=\frac{1}{k+1}\sum_{i=0}^kC_{k+1}^i B_i (n+1)^{k-i+1}$

伯努利数显然可以通过多项式求逆的方式得到,然后就可以用O(k)的时间求出S(n,k)或者用O(k log k)的时间求出S(0,k),...,S(n,k)

同时我们也得到了0~n-1的自然数k次幂和与n^{0,..,k+1}的关系

本文链接: http://www.dtmao.cc/news_show_250304.shtml

附件下载

上一篇：在vscode中打开.md文件

下一篇：Dockerfile---脚本自动化

教程类别

dtcms

文件下载

javascript

.net

编程语言

web前端教程

图片教程

阅读排行

伯努利数,求解自然数幂和的关键系数

正题

附件下载

相关教程

共有条评论网友评论

教程类别

dtcms

文件下载

javascript

.net

编程语言

web前端教程

图片教程

阅读排行

伯努利数,求解自然数幂和的关键系数

正题

附件下载

相关教程

共有条评论 网友评论

共有条评论网友评论