题意
求 $ 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_iprod_{j ot =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 ", Largrange()); return 0; }
预处理逆元阶乘，此时时间复杂度的瓶颈在求前 $k+2$ 项和，所以总的时间复杂度为 $O(klogk)$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxk = 5e4 + 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 inv[maxk], fac[maxk]; //阶乘的逆元 void init() { inv[1] = 1; for(int i = 2;i < maxk; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; //加mod不改变结果 fac[0] = 1; for(int i=1;i< maxk; i++) fac[i]=fac[i-1]*inv[i]%mod; //预处理阶乘 } ll y[maxk]; //前 k+2 项自然数 k 次幂和 也就是yi ll pre[maxk], suf[maxk]; //前缀积 后缀积 ll Largrange() { y[1] = 1; 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]; n %= mod; //因为最后是关于n的多项式 ll ans = 0; pre[0] = suf[k+3] = 1; //边界 for(ll i = 1;i <= k+2;i++) pre[i] = pre[i-1] * (n - i) % mod; for(ll i = k+2;i >= 1;i--) suf[i] = suf[i+1] * (n - i) % mod; for(ll i = 1;i <= k+2;i++) { ll f = fac[i-1] * fac[k+2-i] % mod; f = (k+2-i)&1 ? -f : f; ans = (ans + y[i]*f%mod * pre[i-1]%mod * suf[i+1]%mod + mod) % mod; } return ans; ;} int main() { init(); int T; scanf("%d", &T); while(T--) { scanf("%lld%lld", &n, &k); printf("%lld ", Largrange()); } return 0; }
参考链接：