首页 > 代码库 > 51Nod 1228 序列求和
51Nod 1228 序列求和
T(n) = n^k，S(n) = T(1) + T(2) + ...... T(n)。给出n和k，求S(n)。
例如k = 2，n = 5，S(n) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55。
由于结果很大，输出S(n) Mod 1000000007的结果即可。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 5000)第2 - T + 1行：每行2个数，N, K中间用空格分割。(1 <= N <= 10^18, 1 <= K <= 2000)
Output
共T行，对应S(n) Mod 1000000007的结果。
Input示例
35 34 24 1
Output示例
2253010
数学问题 伯努利数 模板题
用伯努利数可以求自然数幂的和：
$ \sum_{i=1}^{n} i^2 = \frac{1}{k+1}* \sum_{i=1}^{k+1} (C_{k+1}^{k+1-i} *B_{k+1-i}*(n+1)^i) $
伯努利数可以$O(n^2)$递推出来：
$ B_n=-\sum_{k=0}^{n-1} C_{n+1}^{k}*B_k$
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mod=1e9+7; 9 const int mxn=2017;10 LL read(){11 LL x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}14 return x*f;15 }16 LL B[mxn];17 int c[mxn][mxn];18 int ksm(int a,int k){19 int res=1;20 while(k){21 if(k&1)res=(LL)res*a%mod;22 a=(LL)a*a%mod;23 k>>=1;24 }25 return res;26 }27 void init(){28 for(int i=0;i<mxn;i++)c[i][0]=1;29 for(int i=1;i<mxn;i++)30 for(int j=1;j<mxn;j++)31 c[i][j]=((LL)c[i-1][j-1]+c[i-1][j])%mod;32 B[0]=1;33 for(int i=1;i<mxn;i++){34 for(int j=0;j<i;j++)35 B[i]=(B[i]-c[i+1][j]*B[j])%mod;36 int inv=ksm(i+1,mod-2);37 B[i]=B[i]*inv%mod;38 if(B[i]<0)B[i]+=mod;39 }40 return;41 }42 LL n;int k;43 void calc(){44 int res=0;45 int tmp=(n+1)%mod;int bas=tmp;46 for(int i=1;i<=k+1;i++){47 res=((LL)res+(LL)c[k+1][i]*B[k+1-i]%mod*tmp%mod)%mod;48 tmp=(LL)tmp*bas%mod;49 }50 int inv=ksm(k+1,mod-2);51 res=(LL)res*inv%mod;52 printf("%d\n",res);53 return;54 }55 int main(){56 int i,j;57 init();58 int T=read();59 while(T--){60 n=read();k=read();61 calc();62 }63 return 0;64 }
51Nod 1228 序列求和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。