CF 622F The Sum of the k-th Powers——拉格朗日插值

题目：http://codeforces.com/problemset/problem/622/F

发现 sigma(i=1~n) i 是一个二次的多项式( (1+n)*n/2 )，sigma(i=1~n) i^2 是一个三次的多项式，所以 sigma(i=1~n) i^k 是一个k+1次的多项式。用拉格朗日插值就能做了。

注意别弄成 n^2 的。其实就是移动一个位置的时候乘一个数除以一个数，这样的。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e6+,mod=1e9+;

int n,k,a[N],inv[N],ans;

int pw(int x,int k)

{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}

void upd(int &x){x>=mod?x-=mod:;}

int main()

{

  scanf("%d%d",&n,&k); int lm=k+;

  if(n<=lm)

    {

      for(int i=;i<=n;i++)a[i]=a[i-]+pw(i,k),upd(a[i]);

      printf("%d\n",a[n]); return ;

    }

  for(int i=;i<=lm;i++)inv[i]=pw(i,mod-);

  int s0=;

  for(int i=;i<=lm;i++)s0=(ll)s0*(n-i)%mod;

  int s1=,fx=((lm-)&?-:);

  for(int i=;i<=lm;i++)s1=(ll)s1*(i-)%mod;

  a[]=;

  ans=(ll)s0*pw(n-,mod-)%mod*fx*pw(s1,mod-)%mod*a[]%mod;

  for(int i=;i<=lm;i++)

    {

      a[i]=a[i-]+pw(i,k);upd(a[i]);

      fx=-fx;

      s1=(ll)s1*(i-)%mod*inv[lm-i+]%mod;

      ans=(ans+(ll)s0*pw(n-i,mod-)%mod*fx*pw(s1,mod-)%mod*a[i])%mod;

    }

  printf("%d\n",ans<?ans+mod:ans);

  return ;

}