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