给出$n,k$，求$\sum _{i=0}^n i^k$。
方法1：递推
设$s_k(n) = \sum_{i=0}^n i^k$，那么可以推出：
这一步是考虑到$0^k$并不会产生贡献（但是要注意当$k=0$的时候$0^0$要取$1$）。
于是推出了
考虑把$k-1$这一项拿出来，我们就得到了
也就是
这样，对于某一个给定的$n$，我们可以在$O(k^2)$的时间内算出所有的$s_0(n),s_1(n)\cdots s_k(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int cal(ll n,int m) {
static int s[55];
n%=mod;
s[0]=n+1; int pwn=n+1;
for(int k=1;k<=m;++k) {
pwn=pwn*(ll)(n+1)%mod;
s[k]=pwn;
for(int j=0;j<=k-1;++j)
s[k]=(s[k]-C[k+1][j]*(ll)s[j])%mod;
s[k]=s[k]*(ll)Pow(k+1,mod-2)%mod;
}
return s[m];
}
|
方法2：拉格朗日插值
考虑到$\sum_{i=0}^{n}i^m $一定是一个关于$n$的$m+1$次多项式，我们直接把$1,2,\cdots m+2$带入这个多项式，然后插值就可以了。
复杂度$O(m\log mod)$，其中$\log mod$是计算快速幂的复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| ll cal(ll n,int m) {
static ll pre[55],suf[55];
if(n<m+2) {
ll ans=0;
for(int i=1;i<=n;++i)
ans=(ans+Pow(i,m))%mod;
return ans;
}
n%=mod;
ll yi=0,ans=0;
pre[0]=suf[m+3]=1;
for(int i=1;i<=m+2;++i) pre[i]=pre[i-1]*(n-i)%mod;
for(int i=m+2;i>=1;--i) suf[i]=suf[i+1]*(n-i)%mod;
for(int i=1;i<=m+2;++i) {
yi=(yi+Pow(i,m))%mod;
ll tmp=pre[i-1]*suf[i+1]%mod;
ll iv=inv[i-1]*inv[m+2-i]%mod*(((m+2-i)&1)?-1:1);
ans=(ans+tmp*iv%mod*yi)%mod;
}
return (ans%mod+mod)%mod;
}
|
方法3：伯努利数
定义伯努利数$B_0 = 1$，且对于任意的$n>0$，我们有$\sum_{i=0}^n B_i{n+1\choose i} = 0$。通过递推可以在$O(n^2)$的时间内得到每一项。
伯努利数的指数生成函数$B(x)$是$x\over e^x-1$。考虑
这个式子对任意$n>1$成立。注意$B_0=0,B_1=-{1\over 2}$。
上面的式子变形：
也就是说$[x^i]B(x) =[x^i] B(x)*e^x$对于任意$i>1$成立。而$B(x)e^x$的$0$次项的系数是$1$，一次项的系数是$1\over 2$，所以我们得到了$B(x) = B(x)e^x - x$，也就是$B(x)= {x\over e^x - 1}$。
而对于某一个确定的$n$，我们考虑答案关于$k$的指数生成函数：
把$B(x)$带入：
把右边那一项泰勒展开得到的是
然后暴力带回$G(x)$就可以得到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void cal_ber(int n) {
ber[0]=1;
for(int i=1;i<=n;++i) {
ll tmp=0;
for(int j=0;j<i;++j)
tmp=(tmp+ber[j]*(ll)C(i+1,j))%mod;
ber[i]=(mod-tmp)*(ll)Pow(i+1,mod-2)%mod;
}
}
ll cal(ll n,int m) {
ll pn=1,ans=0;
for(int i=0;i<=m;++i) {
pn=pn*(ll)(n+1)%mod;
ans=(ans+C(m+1,m-i)*(ll)ber[m-i]%mod*pn)%mod;
}
ans=ans*Pow(m+1,mod-2)%mod;
return ans;
}
|
方法4：斯特林数
考虑
咕咕咕。
方法 5：生成函数
可以对于某个特定的，在 $O(m\log m)$ 的时间里对所有 $k\in [0,m]$ 的答案。