[题解]CF622F The Sum of the k-th Powers

· · 题解

更好的阅读体验

思路

首先发现 \sum_{i = 1}^{n}i^k 是一个 k + 1 次多项式，那么我们需要求出 k + 2 个点才能得到唯一的一个 f(t) = \sum_{i = 1}^{t}{i^k}。

不难通过拉格朗日插值法，将 x = 1 \sim (k + 2) 的情况一一带入：

f(n) = \sum_{i = 1}^{k + 2}{((\sum_{j = 1}^{i}j^k) \times (\prod_{i \neq j}{\frac{n - x_j}{x_i - x_j}}))}

但是，普通的拉格朗日插值法是 \Theta(k^2)，于是我们需要发掘本题中的特殊性。

可以轻易将原式转化为：

f(n) = \sum_{i = 1}^{k + 2}{((\sum_{j = 1}^{i}j^k) \times \frac{\prod_{i \neq j}{(n - x_j)}}{\prod_{i \neq j}{(x_i - x_j)}})}

发现 x \in [1,k + 2]，那么容易转化：

f(n) = \sum_{i = 1}^{k + 2}{((\sum_{j = 1}^{i}j^k) \times \frac{\prod_{i \neq j}{(n - j)}}{\prod_{i \neq j}{(i - j)}})}

然后你对于 \prod 里面分数的分子、分母分别计算。

对于分子：

\prod_{i \neq j}{(n - x_j)} = \frac{\prod_{j = 1}^{k + 2}(n - j)}{n - i}

然后处理出 \prod_{j = 1}^{k + 2}(n - j) 即可。

对于分母：

\prod_{i \neq j}{(i - j)} = (\prod_{j = 1}^{i - 1}{j}) \times (\prod_{j = -1}^{i - k - 2}{j})

定义 g(i) = (\prod_{j = 1}^{i - 1}{j}) \times (\prod_{j = -1}^{i - k - 2}{j})，考虑 g(i) 与 g(i - 1) 的关系。

发现前一个 \prod 中 g(i) 比 g(i - 1) 多乘以一个 i - 1，后一个 \prod 中 g(i) 比 g(i - 1) 少乘一个 i - k - 3。

因此 g(i) = g(i - 1) \times \frac{i - 1}{i - k - 3}。特别的 g(1) = \prod_{j = -1}^{-k - 1}j

将分子、分母代入原式即可。

观察到当 k + 2 \geq n 时，n - i 会被减成 0，因此需要暴力 \Theta(n) 计算。

Code

#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) ((((a) % mod + (b) % mod) % mod + mod) % mod)
#define Mul(a,b) ((((a) % mod) * ((b) % mod) % mod + mod) % mod)
#define Div(a,b) (Mul(a,qmi(((b) % mod + mod) % mod,mod - 2)))

using namespace std;

const int mod = 1e9 + 7;
int n,k,ans;
int mul = 1,g = 1,y;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int qmi(int a,int b){
    int res = 1;
    while (b){
        if (b & 1) res = Mul(res,a);
        a = Mul(a,a),b >>= 1;
    }
    return res;
}

inline void solve1(){
    for (re int i = 1;i <= n;i++) ans = Add(ans,qmi(i,k));
}

inline void solve2(){
    for (re int i = 1;i <= k + 2;i++) mul = Mul(mul,n - i);
    for (re int i = 1;i <= k + 2;i++){
        y = Add(y,qmi(i,k));
        if (i == 1){
            for (re int j = -1;j >= -k - 1;j--) g = Mul(g,j);
        }
        else g = Mul(g,Div(i - 1,i - k - 3));
        int a = Div(mul,n - i);
        ans = Add(ans,Mul(y,Div(a,g)));
    }
}

signed main(){
    n = read(),k = read();
    if (k + 2 >= n) solve1();
    else solve2();
    printf("%lld",ans);
    return 0;
}