前 n 个正整数的 k 次幂之和为什么是 k+1 次多项式

Imagine · 2018-07-27 15:24:04 · 个人记录

我们从 CF622F The Sum of the k-th Powers 一题说起。

题目为给定 n, k，求 \sum_{i = 1}^{n} i^k\ {\rm mod}\ (10^9 + 7)，n \leq 10^9, k \leq 10^6。这个问题有多种解法，其中一种解法为伯努利数 + 任意模数NTT。但在这里，我们的目的是讨论其与 k+1 次多项式的关系，故使用拉格朗日插值法解决该问题。

如果我们能够确定「前 n 个正整数的 k 次幂之和是 k + 1 次多项式」这一结论是成立的，那么问题就迎刃而解：我们可以直接求出当 n 分别为 1 至 k + 2 时式子的值，之后用拉格朗日插值法解决即可，整个问题的时间复杂度为 O(k)（朴素的插值法为 O(k^2)，但在这里 x 坐标连续，可优化至 O(k)）。如何证明？

令 S(n, k) = \sum_{i = 1}^{n} i^k，那么我们的目的无非是要证明 S(n, k) 与一个关于 n 的 k + 1 次多项式存在等式关系。我们作如下考虑：

• 我们将两个 k + 1 次多项式 (n + 1)^{k + 1} 与 n^{k + 1} 相减，得到： \begin{aligned}(n + 1)^{k + 1}-n^{k + 1} &= \sum_{i = 0}^{k + 1}\left({\begin{matrix}k + 1 \\ i\end{matrix}}\right)n^i - n^{k + 1} \\ &= \sum_{i = 0}^k\left({\begin{matrix}k + 1 \\ i\end{matrix}}\right)n^i \end{aligned}\ \ \ \ \ \ \ \ \ \ \ \cdots(1)其中，(n + 1)^{k + 1} = \sum_{i = 0}^{k + 1}\left(^{k + 1} _ {\ \ \ i\ \ \ }\right)n^i 用到了二项式定理。
• 多项式 n^{k + 1}与 (n - 1)^{k + 1} 相减，得到： n^{k + 1} - (n - 1)^{k + 1} = \sum_{i = 0}^k \left({\begin{matrix}k + 1 \\ i\end{matrix}}\right)(n - 1)^i\ \ \ \ \ \ \ \ \ \ \ \ \cdots(2)
• \cdots
• 多项式 1^{k + 1} 与 0^{k + 1} 相减，得到 1^{k + 1} - 0^{k + 1} = \sum_{i = 0}^k\left({\begin{matrix}k + 1 \\ i\end{matrix}}\right)0^i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots(n + 1)
• 将式子 (1), (2), \cdots ,(n + 1) 相加，得到 (n + 1)^{k + 1} = \sum_{i = 0}^{k}\left({\begin{matrix}k + 1 \\ i\end{matrix}}\right)S(n, i)

由此，我们便不难得到 S(n, i) 与 k + 1 次多项式的关系，自然证明了上面的结论。

CF622F 一题代码如下（由于没有预处理阶乘的逆元，因此该代码的时间复杂度多了一个 \rm log）：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 1e6 + 10, P = 1e9 + 7;

int qpow(int v, int p) {
    int e = 1;
    for (; p; p >>= 1, v = 1ll * v * v % P) if (p & 1) e = 1ll * e * v % P;
    return e;
}

int n, k, fac[maxn], l[maxn], r[maxn];

int lagrange(int v) {
    l[0] = r[k + 3] = 1;
    for (int i = 1; i <= k + 2; i++) l[i] = (1ll * l[i - 1] * (v - i) % P + P) % P;
    for (int i = k + 2; i >= 1; i--) r[i] = (1ll * r[i + 1] * (v - i) % P + P) % P;
    int res = 0, tmp = 0;
    for (int i = 1; i <= k + 2; i++) {
        tmp = (tmp + qpow(i, k)) % P;
        int w = (1ll * tmp * l[i - 1] % P * r[i + 1] % P * qpow(1ll * fac[i - 1] * fac[k + 2 - i] % P, P - 2) * (k + 2 - i & 1 ? -1 : 1) % P + P) % P;
        res = (res + w) % P;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    fac[0] = 1;
    for (int i = 1; i <= k + 2; i++) fac[i] = 1ll * fac[i - 1] * i % P;
    printf("%d\n", lagrange(n));
    return 0;
}