伯努利数求自然数幂和

有时候我们会碰到这样一类问题,求

\sum_{i\ =\ 1}^{n}i^k

当然这次讨论的问题是在模一个大质数意义下。例题链接。好辣,下面开始正题。

 

什么是伯努利数

好吧,直接照抄百科~
设伯努利数为 B_n,它的定义为

\frac{t}{e^t \ -\ 1}\ =\ \sum_{n=0}^{\infty}\frac{B_n}{n!}t^n \ \ \ \    B_0\ =\ 1


其实这和今天的主题并没有什么关系。但伯努利数有个重要的性质:

 \sum_{k=0}^{n} C_{n+1}^{k}B_k\ =\ 0


化简得

 B_n\ =\ -\frac{1}{n+1}(C_{n+1}^{0}B_0\ + C_{n+1}^{1}B_1\ +\ ...\ +\ C_{n+1}^{n-1}B_{n-1})


这样的话在今天的模意义的话题下就能应用了。

 

伯努利数与自然数幂和的关系

有这样的一个公式联系伯努利数和自然数的幂和:

 \sum_{i\ =\ 1}^{n}i^k\ =\ \frac{1}{k+1}\sum_{i=1}^{k+1} C_{k+1}^{i}B_{k+1-i}(n+1)^{i}


有了这个公式,我们就能把幂和分成三个部分分别预处理。最后在线性时间内算出答案来。

第一部分逆元

可以参考递推求逆元

第二部分组合数

利用杨辉三角预处理。

第三部分伯努利数

直接利用上面的公式处理就好。
至于 (n+1)^i 预处理就不用多说了。。。
最后线性求和。这样的话整个问题就能解决啦。

 

例题

题目链接在文章的开始便给出,是裸的练习题,上手很不错。
一次AC,哈哈哈,嘚瑟一下。
2016-02-16 19:14:01 的屏幕截图
 

代码

其中 Inv[N] 是逆元数组 c[N][N] 是组合数 b[N] 是伯努利数 m[N] 是幂数组。

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注