CF622F The Sum of the k-th Powers（拉格朗日插值）

题意

给出 \(n,k\) ， \(n\le10^9,k\le10^6\) ，求 \(\sum_{i=1}^n i^k(mod\;10^9+7)\)

题解

自然数幂次和，是一个\(k+1\)次多项式，那么算出\(k+2\)个值然后差值就行了

//minamoto

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

const int N=1e6+5,P=1e9+7;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

	R int res=1;

	for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);

	return res;

}

int f[N],inv[N];

int n,k;

inline int Inv(R int x){return x<=k?inv[x]:ksm(x,P-2);}

int Large(int k,int n){

	if(k<=n)return f[k];

	int ty=(n&1)?P-1:1,tmp=1,res=0;

	fp(i,1,n)tmp=1ll*tmp*(k-i)%P*Inv(i)%P;

	fp(i,0,n){

		res=add(res,1ll*f[i]*tmp%P*ty%P);

		tmp=1ll*tmp*(k-i)%P*Inv(k-i-1)%P*(n-i)%P*Inv(i+1)%P;

		ty=P-ty;

	}

	return res;

}

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d%d",&n,&k);

	inv[0]=inv[1]=1;fp(i,2,k)inv[i]=1ll*inv[P%i]*(P-P/i)%P;

	fp(i,1,k+1)f[i]=add(f[i-1],ksm(i,k));

	printf("%d\n",Large(n,k+1));

	return 0;

}

巴特西

CF622F The Sum of the k-th Powers（拉格朗日插值）

题意

题解

最新文章

热门文章