CF322F

CF322F

拉格朗日插值
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define M 1100001

#define LL long long

#define P ((LL)1e9+7)

using namespace std;

int n,m,k;

LL f[M],inv[M],Inp[M],Inl[M],A=1,res;

LL qick(LL x,LL y)

{

	LL z=1;

	for(y;y;y>>=1, x=x*x%P) if(y&1) z=z*x%P;

	return z;

}

int main()

{

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

	k=m+2;

	for(int i=1;i<=k;i++) f[i]=(f[i-1]+qick(i,m))%P;

	inv[0]=Inp[0]=inv[1]=Inp[1]=1;

	for(int i=2;i<=k;i++) inv[i]=(P-P/i)*inv[P%i]%P;

	for(int i=1;i<=k;i++) Inp[i]=Inp[i-1]*inv[i]%P;

	for(int i=n;i>=n-k;i--) A=A*i%P;

	if(k>=n) {printf("%I64d",f[n]); return 0;}

	for(int i=1;i<=k;i++)

	{

		int w=qick(n-i,P-2);

		LL Inv=(Inp[i]*Inp[k-i])%P;

		if((k-i)&1) Inv*=-1;

		res=(res+Inv*A%P*w%P*f[i])%P;

	}

	printf("%I64d",(res+P)%P);

}
巴特西

CF322F

最新文章

热门文章
