题目概述

求 $f(n,k)=\sum_{i=1}^{n}i^k$ 。

解题报告

我们知道 $f(n,k)$ 的公式可以由组合数推导，并且由推导方式可知 $f(n,k)$ 是一个 $k+1$ 次多项式，比如：

$$ f(n,1)={n(n+1)\over 2},f(n,2)={n(n+1)(2n+1)\over 6} $$

所以我们可以用 $k+2$ 个点把这个多项式给求出来。

令 $x_i=i,y_i=\sum_{j=1}^{i}j^k$ ，用拉格朗日插值可知：

$$ f(n,k)=\sum_{i=1}^{k+2}y_i\prod_{j\not=i}{n-x_j\over x_i-x_j}=\sum_{i=1}^{k+2}y_i\prod_{j\not=i}{n-i\over i-j} $$

不难发现后面那部分的分子可以预处理+求逆元快速得到，而后面那部分的分母：

$$ (1-2)(1-3)\cdots[1-(k+2)]\\ (2-1)(2-3)\cdots[2-(k+2)] $$

$i$ 和 $i+1$ 除了头和尾之外其他部分是相同的，因此也可以快速转移。

那么对于每个 $n$ 就可以 $O(k\log MOD)$ 得到答案了（ $MOD$ 是模数）。

这种做法比伯努利数好记+好写多了QAQ。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxm=1e6+2,MOD=1e9+7;

int n,m,sum[maxm+5],U,D,INV[maxm+5],ans;

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;} return s;}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m+2;i++) sum[i]=ADD(sum[i-1],Pow(i,m));m+=2;
    if (n<=m) {printf("%d\n",sum[n]);return 0;}
    U=1;for (int i=1;i<=m;i++) U=MUL(U,n-i);
    D=1;for (int i=2;i<=m;i++) D=MUL(D,1+MOD-i);
    for (int i=1;i<=m;i++){
        int now=MUL(MUL(U,Pow(n-i,MOD-2)),Pow(D,MOD-2));
        ans=ADD(ans,MUL(sum[i],now));
        D=MUL(D,MUL(i,Pow(i+MOD-m,MOD-2)));
    }
    printf("%d\n",ans);return 0;
}