F. The Sum of the k-th Powers - 题解

比赛与标签

比赛: Educational Codeforces Round 7 标签: math, *2600 难度: *2600

题目大意喵~

主人你好呀~ 这道题是想让我们计算一个超级大的和的说！∑(っ°Д°;)っ

具体来说，就是给定两个整数 $n$ 和 $k$，我们需要计算 $\sum_{i=1}^{n} i^k = 1^k + 2^k + \dots + n^k$ 的值。

因为 $n$ 可以非常非常大（到 $10^9$ 那么大！），所以结果也可能会是一个天文数字。题目要求我们把最终答案对 $10^9 + 7$ 取模。

输入格式: 一行，包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^9$, $0 \le k \le 10^6$)。

输出格式: 一个整数，表示那个巨大和对 $10^9 + 7$ 取模后的结果。

解题思路大揭秘喵！

看到这么大的 $n$，直接一个一个加肯定是不行的啦，会超时的说！$k$ 的范围也挺大的，所以也不能直接套用低次幂的求和公式。那该怎么办呢？

别急，让本猫娘来给你分析一下！(ฅ'ω'ฅ)

神奇的多项式性质

首先，有一个非常重要的数学结论，主人你一定要记住哦： 自然数幂和 $S_k(x) = \sum_{i=1}^{x} i^k$ 是一个关于 $x$ 的 $k+1$ 次多项式！

举个栗子：

• $k=0: S_0(x) = \sum_{i=1}^{x} 1 = x$，这是一个 1 次多项式。
• $k=1: S_1(x) = \sum_{i=1}^{x} i = \frac{x(x+1)}{2} = \frac{1}{2}x^2 + \frac{1}{2}x$，这是一个 2 次多项式。
• $k=2: S_2(x) = \sum_{i=1}^{x} i^2 = \frac{x(x+1)(2x+1)}{6} = \frac{1}{3}x^3 + \dots$，这是一个 3 次多项式。

看到了吗？规律就是这样喵~

如何确定这个多项式？

既然我们知道 $S_k(n)$ 是一个 $k+1$ 次多项式，那么根据多项式的基本性质，只要我们知道它在 $k+2$ 个不同点上的取值，就可以唯一地确定这个多项式了！

我们可以很方便地计算出 $S_k(x)$ 在 $x=0, 1, 2, \dots, k+1$ 这些点上的值。 令 $y_i = S_k(i) = \sum_{j=1}^{i} j^k$。

• $y_0 = S_k(0) = 0$
• $y_1 = S_k(1) = 1^k = 1$
• $y_2 = S_k(2) = 1^k + 2^k = y_1 + 2^k$
• ...
• $y_i = S_k(i) = y_{i-1} + i^k$

我们可以用 $O(k \log k)$ 的时间通过快速幂预处理出 $y_0, y_1, \dots, y_{k+2}$ 的值。但是！我们还可以更快！用线性筛可以在 $O(k)$ 的时间内预处理出 $1^k, 2^k, \dots, (k+2)^k$ 这些值，然后递推计算出所有的 $y_i$。

拉格朗日插值法登场！

现在我们有了 $k+2$ 个点 $(i, y_i)$（其中 $i=0, 1, \dots, k+1$），目标是求出这个 $k+1$ 次多项式在 $x=n$ 处的值。这时候，就是拉格朗日插值法大显身手的时候啦！

拉格朗日插值的公式是长这样的： $S_k(n) = \sum_{j=0}^{k+1} y_j \cdot L_j(n)$ 其中 $L_j(n)$ 是拉格朗日基函数： $L_j(n) = \prod_{i=0, i \neq j}^{k+1} \frac{n-i}{j-i}$

我们来把它拆解一下，让它变得更可爱、更容易计算喵~ $L_j(n) = \left( \prod_{i=0, i \neq j}^{k+1} (n-i) \right) \cdot \left( \prod_{i=0, i \neq j}^{k+1} (j-i)^{-1} \right)$

分子部分: $\prod_{i=0, i \neq j}^{k+1} (n-i)$ 直接计算太慢了。我们可以预处理出前缀积 pref[x] = $\prod_{i=0}^{x} (n-i)$ 和后缀积 suff[x] = $\prod_{i=x}^{k+1} (n-i)$。 那么分子就等于 pref[j-1] * suff[j+1] 啦！这样每次计算分子就是 $O(1)$ 的了。

分母部分: $\prod_{i=0, i \neq j}^{k+1} (j-i)$ 这个可以拆成两部分：

• $\prod_{i=0}^{j-1} (j-i) = (j-0)(j-1)\dots(j-(j-1)) = j \cdot (j-1) \dots 1 = j!$
• $\prod_{i=j+1}^{k+1} (j-i) = (j-(j+1))(j-(j+2))\dots(j-(k+1)) = (-1)(-2)\dots(-(k+1-j)) = (-1)^{k+1-j} \cdot (k+1-j)!$

所以，分母就是 $j! \cdot (k+1-j)! \cdot (-1)^{k+1-j}$。 因为我们是在模意义下计算，除法要变成乘以它的模逆元。阶乘和阶乘的逆元都可以预处理出来。

总结一下步骤

1. 特判: 如果 $k=0$，答案就是 $n \pmod{MOD}$。
2. 预处理点值: 用线性筛求出 $i^k \pmod{MOD}$ for $i=1, \dots, k+2$。然后递推求出 $y_i = S_k(i)$ for $i=0, \dots, k+2$。
3. 小n特判: 如果 $n \le k+2$，我们已经直接算出了答案 $y_n$，直接输出就好啦。
4. 拉格朗日插值:
   • 预处理阶乘和阶乘的逆元。
   • 预处理分子需要的前缀积和后缀积。
   • 循环 $j$ from $0$ to $k+1$，根据上面的公式计算每一项 $y_j \cdot L_j(n)$，然后累加起来。
   • 注意 $(-1)^{k+1-j}$ 的符号！如果 $k+1-j$ 是奇数，就要减去这一项（在模意义下就是加上它的相反数）。
5. 输出最终的累加和，任务完成喵！

AC代码奉上喵~

#include <iostream>
#include <vector>
#include <numeric>

// 快速幂函数，用于计算 (base^exp) % MOD，喵~
long long power(long long base, long long exp);

// 费马小定理求模逆元，(n^(MOD-2)) % MOD
long long inv(long long n);

// 常量定义
const int MOD = 1e9 + 7;
const int MAX_K = 1e6 + 5;

// 全局变量
long long n;
int k;

// 预处理数组
long long fact[MAX_K];       // 存储阶乘
long long inv_fact[MAX_K];   // 存储阶乘的逆元
int lp[MAX_K];               // 线性筛用的，存储每个数的最小质因子
long long pw[MAX_K];         // 存储 i^k
long long y[MAX_K];          // 存储点值 S_k(i) = sum_{j=1 to i} j^k
long long pref_n[MAX_K];     // 拉格朗日插值用的前缀积 (n-0)*(n-1)*...
long long suff_n[MAX_K];     // 拉格朗日插值用的后缀积 ...*(n-(d-1))*(n-d)

// 预处理阶乘和它们的模逆元
void precompute_factorials(int limit) {
    fact[0] = 1;
    for (int i = 1; i <= limit; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    inv_fact[limit] = inv(fact[limit]);
    for (int i = limit - 1; i >= 0; --i) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

// 线性筛，用于快速计算 i^k
void sieve(int limit) {
    std::vector<int> primes;
    std::fill(lp, lp + limit + 1, 0);
    for (int i = 2; i <= limit; ++i) {
        if (lp[i] == 0) {
            lp[i] = i; // i是质数
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > lp[i] || (long long)i * p > limit) {
                break;
            }
            lp[i * p] = p;
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> k;

    // k=0 的特殊情况，sum = 1+1+...+1 = n
    if (k == 0) {
        std::cout << n % MOD << std::endl;
        return 0;
    }

    // 求和公式是一个 k+1 次多项式，我们需要 k+2 个点来确定它
    // 我们用点 (i, S_k(i)) for i = 0, ..., k+1
    // 这里我们算到 k+2 是为了方便处理 n <= k+2 的情况
    int limit = k + 2;

    // 线性筛预处理，然后计算 i^k
    sieve(limit);
    pw[1] = 1;
    for (int i = 2; i <= limit; ++i) {
        if (lp[i] == i) { // i 是质数，直接用快速幂
            pw[i] = power(i, k);
        } else { // i 是合数，用性质 pw[i] = pw[lp[i]] * pw[i/lp[i]]
            pw[i] = (pw[lp[i]] * pw[i / lp[i]]) % MOD;
        }
    }

    // 计算点值 y[i] = S_k(i) = sum_{j=1 to i} j^k
    y[0] = 0;
    for (int i = 1; i <= limit; ++i) {
        y[i] = (y[i - 1] + pw[i]) % MOD;
    }

    // 如果 n 比较小，我们已经直接算出了答案，可以直接输出喵
    if (n <= limit) {
        std::cout << y[n] << std::endl;
        return 0;
    }

    // 如果 n 很大，就要用拉格朗日插值法了
    int d = k + 1; // 多项式的次数
    precompute_factorials(limit);

    long long n_mod = n % MOD;

    // 预计算分子中的 (n-i) 的前缀积
    pref_n[0] = n_mod;
    for (int i = 1; i <= d; ++i) {
        pref_n[i] = (pref_n[i - 1] * (n_mod - i + MOD)) % MOD;
    }

    // 预计算分子中的 (n-i) 的后缀积
    suff_n[d] = (n_mod - d + MOD) % MOD;
    for (int i = d - 1; i >= 0; --i) {
        suff_n[i] = (suff_n[i + 1] * (n_mod - i + MOD)) % MOD;
    }

    long long total_sum = 0;
    // 拉格朗日插值求和
    for (int j = 0; j <= d; ++j) {
        // 计算分子部分 prod_{i!=j} (n-i)
        long long num_val = 1;
        if (j > 0) {
            num_val = (num_val * pref_n[j - 1]) % MOD;
        }
        if (j < d) {
            num_val = (num_val * suff_n[j + 1]) % MOD;
        }

        // 计算分母的逆元 (j! * (d-j)!)^{-1}
        long long den_inv_val = (inv_fact[j] * inv_fact[d - j]) % MOD;

        // 组合成一项
        long long term = (y[j] * num_val) % MOD;
        term = (term * den_inv_val) % MOD;

        // 处理符号 (-1)^(d-j)
        if ((d - j) % 2 == 1) {
            term = (MOD - term) % MOD;
        }

        total_sum = (total_sum + term) % MOD;
    }

    std::cout << total_sum << std::endl;

    return 0;
}

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long inv(long long n) {
    return power(n, MOD - 2);
}

复杂度分析时间到！

• 时间复杂度: O(k) 的说。

  • 线性筛求 $i^k$ 是 $O(k)$。
  • 递推计算点值 $y_i$ 是 $O(k)$。
  • 预处理阶乘和逆元是 $O(k)$。
  • 预处理前后缀积是 $O(k)$。
  • 最后的拉格朗日插值循环是 $O(k)$。
  • 所以总的时间复杂度就是 $O(k)$ 啦，非常快！

• 空间复杂度: O(k) 的说。

  • 我们需要几个大小为 $O(k)$ 的数组来存储阶乘、逆元、幂次、点值等等。所以空间复杂度也是 $O(k)$。

猫娘的小课堂时间~

这道题真是一道非常经典的数论好题，融合了好几个知识点呢！让本猫娘来给你总结一下吧~

1. 核心思想: 降维打击！把一个看似需要 $O(n)$ 计算的求和问题，通过发现其内在的多项式性质，转化为了一个只和 $k$ 相关的问题。这是算法竞赛中一个非常重要的思想呐！

2. 关键算法: 拉格朗日插值法。这是解决“已知一个多项式在若干点上的取值，求其在另一点的取值”问题的标准武器。主人一定要掌握它的公式和推导过程哦！

3. 优化技巧:

   • 线性筛求幂: 相比于对每个数都用快速幂，线性筛利用积性函数的性质，可以在 $O(k)$ 时间内求出 $1^k, \dots, k^k$，是本题时间复杂度能达到 $O(k)$ 的关键之一。
   • 前后缀积优化: 在计算拉格朗日基函数 $L_j(n)$ 的分子时，使用前后缀积将每次 $O(k)$ 的计算优化到了 $O(1)$，大大提高了效率。

4. 注意事项:

   • 模运算: 全程都要记得取模，特别是减法可能出现负数，要写成 (a - b + MOD) % MOD 的形式才安全。
   • 逆元: 除以一个数等于乘以它的模逆元。对于质数模数，费马小定理是你的好朋友！
   • 边界处理: $k=0$ 和 $n \le k+2$ 的情况要单独处理，这样能简化代码逻辑，还能防止一些奇奇怪怪的错误。

希望这篇题解能帮到主人你哦！遇到难题不要怕，只要我们一步一步分析，总能找到解决方法的喵~ 加油！(๑•̀ㅂ•́)و✧