CF622F The Sum of the k-th Powers 题解

题目链接：The Sum of the k-th Powers

题意：

给定 \(n,k\) ，求 \[ f(n,k)=\sum_{i=1}^ni^k \pmod{10^9+7} \] 数据范围：\(1 \le n \le 10 ^ 9, 0 \le k \le 10 ^ 6\)。

考虑 \(k\) 固定时的情况。可以证明，函数 \(f(n) = \sum_{i=1}^ni^k\) 是一个 \(k+1\) 次多项式。

证明 考虑把 \(\sum_{i=1}^n i^k\) 看作 \(n^k+(n-1)^k + \cdots + (n-(n-1))^k\)

暴力展开以后，可以发现这是 \(n\) 个 \(k\) 次多项式，即 \(k+1\) 次多项式。\(\square\)

由于 \(k\) 比较小，所以考虑随便找 \(k+2\) 个点（取 \(n=1,2\cdots,k+2\) 即可）代入

因为 \(k+2\) 个点 \((x_i,y_i)\) 可以唯一确定 \(k+1\) 次多项式，根据拉格朗日插值法可知 \[ f(n)=\sum_{i=1}^{k+2} y_i \prod_{j \neq i} \frac{n-x_j}{x_i-x_j} \] 这里因为代入的是 \(1,2,\cdots\) 所以可以用阶乘以及前/后缀积来预处理。

时间复杂度 \(\mathcal{O}(k \log k)\) ，用线性筛预处理 \(i^k\) 和逆元可以做到 \(\mathcal{O}(k)\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
int mi(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

int pre[N], suf[N], fac[N]; 
int qpow(int a, int b)
{
    int r = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, k; cin >> n >> k;
    pre[0] = suf[k + 3] = fac[0] = 1;
    rep(i, 1, k + 2) pre[i] = pre[i - 1] * mi(n, i) % mod;
    Rep(i, k + 2, 1) suf[i] = suf[i + 1] * mi(n, i) % mod;
    rep(i, 1, k + 2) fac[i] = fac[i - 1] * i % mod;
    int y = 0, res = 0;
    rep(i, 1, k + 2)
    {
        add(y, qpow(i, k));
        const int _1 = pre[i - 1] * suf[i + 1] % mod;
        const int _2 = fac[i - 1] * (((k - i) & 1) ? mod - 1 : 1) % mod * fac[k + 2 - i] % mod;
        add(res, y * _1 % mod * qpow(_2, mod - 2) % mod);
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/bgaterib