自然数幂和&伯努利数(Bernoulli)
2024-09-05 12:01:21
二项式定理求自然数幂和
由二项式定理展开得
\[(n+1)^{k+1}-n^{k+1}=\binom {k+1}1n^k+\binom {k+1}2n^{k-1}+\cdots+\binom {k+1}kn+1
\]
\]
那么,对于所有的\(n=1,2,3,\cdots\)累加得到
\[(n+1)^{k+1}-1=\binom{k+1}1\sum_{i=1}^ni^k+\binom{k+1}2\sum_{i=1}^ni^{k-1}+\cdots+\binom {k+1}k\sum_{i=1}^ni+n
\]
\]
进一步得到
\[\sum_{i=1}^ni^k=\frac1{k+1}[(n+1)^{k+1}-(\binom{k+1}2\sum_{i=1}^ni^{k-1}+\cdots+\binom {k+1}k\sum_{i=1}^ni+n+1)]
\]
\]
计\(S(n,k)=\sum_{i=1}^ni^k\),可以得到
\[S(n,k)=\frac1{k+1}[(n+1)^{k+1}-(\binom{k+1}2S(n,k-1)+\cdots+\binom {k+1}kS(n,1)+n+1)]
\]
\]
当\(k==1\),有\(S(n,1)=\frac{n\cdot(n+1)}{2}\)。
加入记忆化即可。
伯努利数
\[\sum_{i=1}^ni^k=\frac{1}{k+1}\sum_{i=1}^{k+1}\binom {k+1}iB_{k+1-i}(n+1)^i
\]
\]
伯努利数满足\(B_0=1\),且有
\[\sum_{k=0}^n\binom{n+1}kB_k=0
\]
\]
那么有
\[B_n=-\frac1{n+1}(\binom{n+1}0B_0+\binom{n+1}1B_1+\dots+\binom{n+1}{n-1}B_{n-1})
\]
\]
这样就可以\(O(n^2)\)预处理出伯努利数。
还可以对\(B_i\)构建指数型生成函数
\[B(x)=\sum_{i=0}^\infty \frac{B_i}{i!}x^i
\]
\]
经过我也不懂得化简得到
\[\begin{split}
B(x)=\frac{x}{e^x-1}\\
B[x]=ifac[x+1]
\end{split}
\]
B(x)=\frac{x}{e^x-1}\\
B[x]=ifac[x+1]
\end{split}
\]
可以利用多项式求逆在\(O(n\log n)\)计算伯努利数。
例题 51nod 1228 序列求和
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=10005,K=2005,mod=1e9+7;
using namespace std;
inline LL Getint(){register LL x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
int inv[N],fac[N],ifac[N],B[N];
int C(int n,int m){
if(n<m)return 0;
return (LL)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int S(LL n,int k){
int ret=0;
LL ori=(n+1)%mod,fac=ori;
for(int i=1;i<=k+1;i++,fac=(LL)fac*ori%mod)
ret=(ret+(LL)C(k+1,i)*B[k+1-i]%mod*fac)%mod;
return (LL)(ret+mod)%mod*inv[k+1]%mod;
}
int main(){
inv[1]=fac[0]=ifac[0]=1;
for(int i=2;i<=K;i++)inv[i]=(LL)inv[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=K;i++)fac[i]=(LL)fac[i-1]*i%mod;
for(int i=1;i<=K;i++)ifac[i]=(LL)ifac[i-1]*inv[i]%mod;
B[0]=1;
for(int i=1;i<=K;i++){
for(int j=0;j<i;j++)
B[i]=(B[i]-(LL)B[j]*C(i+1,j))%mod;
B[i]=(LL)B[i]*inv[i+1]%mod;
}
int T=Getint();
while(T--){
LL n=Getint(),k=Getint();
cout<<S(n,k)<<'\n';
}
return 0;
}
最新文章
- Angular2学习笔记——NgModule
- Unity在PC上创建Excel文档
- [原创]java WEB学习笔记92:Hibernate学习之路-- -QBC 检索和本地 SQL 检索:基本的QBC 查询,带 AND 和 OR 的QBC,统计查询,排序,分页
- AppCache 离线存储 应用程序缓存 API 及注意事项
- AD组策略添加本地账号、设置允许ping回显
- javascript jquery 常用方法
- bash shell漏洞及测试
- unity3d设置3D模型显示在2D背景之前(多个相机分层显示)(转)
- java与javax有什么区别?
- Android(java)学习笔记247:ContentProvider使用之利用ContentProvider备份和还原手机短信(掌握)
- 构建你的第一个App
- intellij中javax包的导入
- 【ASP.NET MVC 学习笔记】- 16 Model Binding(模型绑定)
- 串String(1):串的实现(定长顺序存储结构)
- bootstrap模态框内容替换时会重新触发模态框?<;a>;标签到底有哪些特殊的特性呢?
- Android事件机制之二:onTouch详解
- mysql bigint ,int , smallint,tinyint 的范围
- 使用HttpClient消费ASP.NET Web API服务
- code vs 2639 约会计划
- springcloud中eureka集群unavailable-replicas