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

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

L (x) = \sum i = 1 k + 2 p (i) ? l (i)

$L(x)=\sum_{i=1}^{k+2}p(i)*l(i)$
其中

p (i) = \sum j = 1 i j k

$p(i)=\sum_{j=1}^ij^k$

l (i) = \prod j = 1, j \neq i k + 2 n ? j i ? j

$l(i)=\prod_{j=1,j\neq i}^{k+2} \frac{n-j}{i-j}$
令

c=∏k+2i=1(n?i) $c=\prod_{i=1}^{k+2}(n-i)$ ，分母转化为两个阶乘的形式，注意正负号，可得

l (i) = c ? (n ? i) ? 1 ? (i ? 1)! ? 1 ? (k + 2 ? i)! ? 1 ? (? 1) k + 2 ? i

$l(i)=c*(n-i)^{-1}*(i-1)!^{-1}*(k+2-i)!^{-1}*(-1)^{k+2-i}$
预处理出阶乘，逆元，p数组即可，复杂度

O(klogk) $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;
}