题解 CF622F 【The Sum of the k-th Powers】
HenryHuang
2020-06-16 17:58:38
### 题意
求 $\sum_{i=1}^ni^k(1\le n\le 10^9,0\le k\le 10^6)$。
### 题解
不要以为没人会卡 $O(k\log_2k)$ 做法的...
真的有这种毒瘤...
首先 $O(k\log_2k)$ 的做法及证明其他题解都已经讲的很清楚了，在这里不再赘述。
首先如何考虑求出插值所需要的点值，即当 $n=1,2,\cdots,k+2$ 时的值。
注意到 $f(i)=i^k$ 是一个完全积性函数，所以我们只需要求出当 $i$ 为质数时候的值，然后线性筛即可，最后做一遍前缀和即可得到答案。这样的复杂度大约是 $O(k)$ 的，因为我们只在质数的位置进行了快速幂。
由于我们取的是一段连续的点值，所以在插值的时候只需要维护一个前缀积、后缀积、阶乘及阶乘逆元即可。
线性求逆元大概就是先求出 $\frac {1}{n!}$，然后 $\frac {1}{(n-1)!}=\frac {1}{n!}\times n$。事实上这个方法可以在线性时间内处理出任意的 $n$ 个已知数的逆元。
然后这个题就完了，总时间复杂度为 $O(k)$。
贴代码
```
/*---Author:HenryHuang---*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int p=1e9+7;
int n,k;
int ksm(int a,int b,int p){
int ans=1;
while(b){
if(b&1) ans=1ll*ans*a%p;
b>>=1,a=1ll*a*a%p;
}
return ans;
}
int pri[maxn],mi[maxn],cnt;
bool P[maxn];
void init(){
mi[1]=1;
for(int i=2;i<=k+2;++i){
if(!P[i]) mi[i]=ksm(i,k,p),pri[++cnt]=i;
for(int j=1;j<=cnt&&i*pri[j]<=k+2;++j){
P[i*pri[j]]=1;
mi[i*pri[j]]=1ll*mi[i]*mi[pri[j]]%p;
if(i%pri[j]==0) break;
}
}
for(int i=1;i<=k+2;++i) mi[i]=(mi[i]+mi[i-1]>p?mi[i]+mi[i-1]-p:mi[i]+mi[i-1]);
}
int f[maxn],g[maxn];
int fac[maxn],inv[maxn],ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
init();
f[0]=g[0]=1;
if(n<=k+2) cout<<mi[n]<<'\n',exit(0);
f[0]=g[k+3]=fac[0]=inv[0]=1;
for(int i=1;i<=k+2;++i) f[i]=1ll*f[i-1]*(n-i)%p;
for(int i=k+2;i>=1;--i) g[i]=1ll*g[i+1]*(n-i)%p;
for(int i=1;i<=k+2;++i) fac[i]=1ll*fac[i-1]*i%p;
inv[k+2]=ksm(fac[k+2],p-2,p);
for(int i=k+1;i>=1;--i) inv[i]=1ll*inv[i+1]*(i+1)%p;
for(int i=1;i<=k+2;++i){
int a=1ll*f[i-1]*g[i+1]%p;
int b=1ll*inv[i-1]*((k-i)&1?(p-inv[k+2-i]):inv[k+2-i])%p;
ans=(ans+1ll*mi[i]*a%p*b%p)%p;
}
cout<<ans<<'\n';
return 0;
}
```