IX.CF622F The Sum of the k-th Powers

看上去这题是上一题的弱化版，但其实不是——上题我们要筛出式子，但是这题我们要保证复杂度。

首先，我们打算选取\(0\sim k+1\)，共\(k+2\)个点进行插值。我们设\(f_x=\sum\limits_{i=0}^x i^k\)。

则由拉格朗日插值公式，我们有答案等于

\[\sum\limits_{i=0}^{k+1}f_il_i(n) \]

展开得到

\[\sum\limits_{i=0}^{k+1}f_i\prod\limits_{j\neq i}\dfrac{n-j}{i-j} \]

分子上的东西，我们可以通过预处理\(w=\prod n-i\)，然后就变成了\(\dfrac{w}{n-i}\)。

分母上的东西，我们观察到它实际上是阶乘的形式，于是最终答案就变成了

\[\sum\limits_{i=0}^{k+1}f_i\dfrac{w}{(n-i)\times i!\times(k+1-i)!\times(-1)^{k+1-i}} \]

于是直接按照上式计算即可。

时间复杂度\(O(k\log k)\)，瓶颈在于求逆元要\(O(\log k)\)。

代码（极致压行版）：

#include<bits/stdc++.h>
const int mod=1e9+7;
int n,m,a[1001000],res,prod=1,fac[1001000],inv[1001000];
int ksm(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int main(){
	scanf("%d%d",&n,&m),fac[0]=1;
	for(int i=1;i<=m+1;i++)a[i]=(ksm(i,m)+a[i-1])%mod,fac[i]=1ll*fac[i-1]*i%mod;
	if(n<=m+1){printf("%d\n",a[n]);return 0;}
	for(int i=0;i<=m+1;i++)prod=1ll*prod*(n-i+mod)%mod;
	inv[m+1]=ksm(fac[m+1],mod-2);
	for(int i=m;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	for(int i=0;i<=m+1;i++)(res+=1ll*a[i]*prod%mod*ksm((n-i+mod)%mod,mod-2)%mod*(((m+1-i)&1)?mod-inv[m+1-i]:inv[m+1-i])%mod*inv[i]%mod)%=mod;
	printf("%d\n",res);
	return 0;
}