题意
求 $ \displaystyle \sum_{i=1}^n i^k \ mod (1e9+7), n \leq 10^9, k \leq 10^6$.
分析
易知答案是一个 $k+1$ 次多项式，我们找 $k+2$ 个值代进去，然后拉格朗日插值。
$n+1$ 组点值对 $(x_i, y_i)$，得到 $n$ 次多项式 $f$ 的拉格朗日插值公式为：
$$f(x) = \sum_{i = 0}^n y_i\prod_{j\not =i} \frac{x-x_j}{x_i-x_j}$$
时间复杂度为 $O(n^2)$，
如果我们取 $n$ 个连续的值，这样可以预处理阶乘，复杂度降至 $O(n)$，
在这题中复杂度为 $O(k log{mod})$，其中 $O(log mod)$为求逆元的时间。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxk = 1000000 + 10; ll n, k; ll qpow(ll m, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = (res * m) % mod; m = (m * m) % mod; n = n >> 1; } return res; } ll fac[maxk], y[maxk]; //前k+2项前缀和都已经算好 ll Largrange() { fac[0]=fac[1]=1,y[1]=1; for(int i=2;i<=k+2;i++) fac[i]=fac[i-1]*i%mod; //预处理阶乘 for(int i=2;i<=k+2;i++) y[i]=(y[i-1]+qpow(i,k, mod))%mod; //预处理求出每一项的结果 if(n<=k+2) return y[n]; ll ans = 0, prod = 1, sig; for(ll i = n-k-2; i <= n-1;i++) prod = prod * i % mod; for(ll i = 1;i <= k+2;i++) { ll fz = prod * qpow(n-i, mod-2, mod) % mod; ll fm = qpow(fac[i-1] * fac[k+2-i] % mod, mod-2, mod); if((k+2-i) % 2 == 0) sig = 1; else sig = -1; ans = (ans + sig*y[i]*fz%mod*fm%mod + 2*mod) % mod; } return ans; ;} int main() { scanf("%lld%lld", &n, &k); printf("%lld\n", Largrange()); return 0; }
参考链接：