解题思路
比较经典的一道题目。第一种方法是差分，就是假设\(k=3\)，我们打一个表。
0 1 9 36 100 225 1 8 27 64 125 7 19 37 61 12 18 24 6 6
表中第一行为所要求的前缀和，后面的\(f[i][j]=f[i-1][j]+f[i-1][j-1]\)，就是每个数字等于上面的数字\(-\)左上的数字，减到最后发现只剩一样的数字。此时第一行的后面的所有数字只与后面每一行的第一个数字有关，而且系数恰好是一个组合数。比如说我们要算第一行第\(10\)个数字，也就是\(n=10\)的时候的答案。那么
\[ ans=C(10,1)*1+C(10,2)*7+C(10,3)*12+C(10,4)*6 \] 这个的证明可以根据实际意义来，从第二行第一个数字到第一行第十个数字一共走\(10\)步，期中\(1\)步向上走，那么就为\(C(10,1)\)。所以我们暴力算出前\(k+1\)项的值，然后递推即可。差分法的时间复杂度为\(O(k^2)\)的，无法通过此题。但是这个思想值得学习。
#include#include #include #include #define int long longusing namespace std;const int MAXN = 1005;const int MOD = 1e9+7;int n,k,inv[MAXN],fac[MAXN];int f[MAXN][MAXN],ans;inline int fast_pow(int x,int y){ int ret=1; for(;y;y>>=1){ if(y&1) ret=ret*x%MOD; x=x*x%MOD; } return ret;}inline int C(int n,int m){ return fac[n]*inv[m]%MOD*inv[n-m]%MOD;}signed main(){ scanf("%lld%lld",&n,&k);fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;inv[n]=fast_pow(fac[n],MOD-2); for(int i=n-1;~i;i--) inv[i]=inv[i+1]*(i+1)%MOD; for(int i=1;i<=k+1;i++) f[0][i]=f[0][i-1]+fast_pow(i,k),f[0][i]%=MOD; if(n<=k+1) {printf("%lld\n",f[0][n]);return 0;} for(int i=1;i<=k+1;i++) for(int j=i;j<=k+1;j++) f[i][j]=f[i-1][j]-f[i-1][j-1],f[i][j]=(f[i][j]+MOD)%MOD; for(int i=1;i<=k+1;i++) ans=(ans+f[i][i]*C(n,i)%MOD)%MOD; printf("%lld\n",ans); return 0;}
第二种方法自然就是拉格朗日插值法，对于一段连续的值来说，拉格朗日插值法可以在\(O(k)\)内解决，具体来说就是将定义式变形。
\[ \prod\limits_{i!=j} \frac{x-x_j}{x_i-x_j} \] 因为带入的值是连续的，所以上面一定是两段连续的乘积，我们要维护一个前缀乘积后缀乘积拼起来。下面的话可以看成两个阶乘，正负取决于\(n-i\)的奇偶性，这样就可以\(O(n)\)的算出结果。#include#include #include #include #include #define int long longusing namespace std;const int MAXN = 1000005;const int MOD = 1e9+7;int n,k,inv[MAXN],y[MAXN];int pre[MAXN],suf[MAXN],ans,fac[MAXN];int fast_pow(int x,int y){ int ret=1; for(;y;y>>=1){ if(y&1) ret=ret*x%MOD; x=x*x%MOD; } return ret;}signed main(){ scanf("%lld%lld",&n,&k); pre[0]=1;for(int i=1;i<=k+2;i++) pre[i]=pre[i-1]*(n-i)%MOD; suf[k+3]=1;for(int i=k+2;i;i--) suf[i]=suf[i+1]*(n-i)%MOD; fac[0]=1;for(int i=1;i<=k+2;i++) fac[i]=fac[i-1]*i%MOD; inv[k+2]=fast_pow(fac[k+2],MOD-2); for(int i=k+1;~i;i--) inv[i]=inv[i+1]*(i+1)%MOD;int s1,s2; for(int i=1;i<=k+2;i++) y[i]=(y[i-1]+fast_pow(i,k))%MOD; for(int i=1;i<=k+2;i++){ s1=pre[i-1]*suf[i+1]%MOD; s2=inv[i-1]*inv[k+2-i]*(((k+2-i)&1)?-1:1)%MOD; ans=((ans+s1*s2%MOD*y[i]%MOD)%MOD+MOD)%MOD; } printf("%lld\n",ans); return 0;}