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

题目链接：传送门
题意：求 ∑ni=1ik 
题解：
找规律可以发现前n项k次幂的和一定能用一个k+1次多项式表示出来，所以可以暴力地求出前k+2所对应的值，再用拉格朗日插值法求解即可

<nobr> L (x) = \sum i = 1 k + 2 p (i) * l (i) </nobr>

其中

<nobr> p (i) = \sum j = 1 i j k </nobr>

<nobr> l (i) = \prod j = 1, j \neq i k + 2 n - j i - j </nobr>

令 c=∏k+2i=1(n−i) ，分母转化为两个阶乘的形式，注意正负号，可得

<nobr> l (i) = c * (n - i) - 1 * (i - 1)! - 1 * (k + 2 - i)! - 1 * (- 1) k + 2 - i </nobr>

预处理出阶乘，逆元，p数组即可，复杂度 O(klogk)

//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=1000100,mod=1e9+7;
LL n,k,fac[N],inv[N],c,p[N];
inline int in()
{
    char ch=getchar();
    int f=1,tmp=0;
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}
    return tmp*f;
}

LL ksm(LL a,LL b)
{
    LL ret=1;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}

int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=k+2;i++) p[i]=(p[i-1]+ksm(i,k))%mod;
    if(n<=k+2) {printf("%lld",p[n]);return 0;}
    fac[0]=inv[0]=c=1;
    for(int i=1;i<=k+2;i++) fac[i]=fac[i-1]*i%mod;
    inv[k+2]=ksm(fac[k+2],mod-2);
    for(int i=k+1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<=k+2;i++) c=c*(n-i)%mod;
    LL ans=0;
    for(int i=1;i<=k+2;i++)
        ans+=p[i]*c%mod*ksm(n-i,mod-2)%mod*inv[i-1]%mod*inv[k+2-i]%mod*((k+2-i)%2==0?1:-1)%mod;ans=ans%mod;
    printf("%lld",(ans+mod)%mod);
    return 0;
}