centos8 audio 百度seo关键词优化 jquery去除空格 jquery通过class获取元素 matlab注释一段 hbase端口 matlab颜色代码 matlab生成对角矩阵 idea批量替换快捷键 mysql重启 python正则表达式 python逻辑运算符 python类与对象 python字典添加 python正则匹配数字 python如何定义变量 stringjava java变量 java中泛型 java语言介绍 java时间戳转日期 java多线程处理 java创建文件夹 python源码下载 心理学与生活下载 java电子书下载 亚索刀光特效包 神龙kms js转int c语言表白代码 在线手册 凤凰刷机 视频编辑专家下载 ps扭曲变形 深入解析windows操作系统 数据结构与算法分析 1500左右性价比最高的手机 上单艾克出装 x截屏
当前位置: 首页 > 学习教程  > 编程语言

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

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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?