无所畏惧的求和题解

本题是本人目前出的题中难度最高的题。

可能可以评一个黑？可能有点过，但是紫色是肯定可以的。

题目链接：无所畏惧的求和 - 洛谷

尽情享受吧！

这道题其实做法有很多：

  • 待定系数法 + 矩阵求解 推代数公式

  • 组合数学 + 待定系数法 推组合公式

  • 第一类斯特林数（时间复杂度可能有点问题，为 \(O(k^2)\)

  • 拉格朗日插值法&牛顿插值法（我表示我不会）

  • 伯努利数（奇奇怪怪）

  • ……

那么这里讲解前两种方式

代数公式

自然数幂方求和公式？在高等教育出版社出版的《数学手册》中有这么一些公式：

采用万能的数学归纳法可以一一证明上述公式。此处不提。

但是观察上述公式，可以发现一个特征：自然数 \(k\) 次幂求和公式是关于 \(n\) 的 \(k + 1\) 次有理多项式。

也就是

\[\sum_{i=1}^n i^k = \sum_{j=1}^{k+1} a_j n^{j}
\]

知道上述结果之后，可采用待定系数法，也就是写出 \(n = 1, 2, 3, \dots, k+1\) 的 \(k + 1\) 个代数式，利用矩阵求解即可。

举个例子，对于 \(k = 3\) 的情况：

\[\begin{aligned}
\sum_{i=1}^1 i^3 &= a_1 + a_2 + a_3 + a_4 &= 1 \\
\sum_{i=1}^2 i^3 &= 2a_1 + 4a_2 + 8a_3 + 16a_4 &= 9 \\
\sum_{i=1}^3 i^3 &= 3a_1 + 9a_2 + 27a_3 + 81a_4 &= 36 \\
\sum_{i=1}^4 i^3 &= 4a_1 + 16a_2 + 64a_3 + 256a_4 &= 81 \\
\end{aligned}
\]

那么借此求出每一项的系数即可对于每一个询问在 \(O(k)\) 的复杂度内完成计算。

总的复杂度为 \(O(k^3 + T \cdot k)\)。但是，很明显，对于每一个测试点不会有所有的 \(k\)。所以请在必要时再计算系数。

组合公式

这个方法相对优秀一点点。标程就是用的此写法。

其实不难发现，对于 \(x^k\)，我们可以改写为：

\[x^k = \sum_{i=1}^{k} a_i\binom{k}i
\]

那么依据某些公式推导：

\[\sum_{x=1}^n x^k = \sum_{i = 2}^{k + 1} a_{i-1} \binom {n+1}i
\]

所以，类似的，我们也可以枚举 \(n = 1, 2, 3, \dots, k\) 来寻找其系数：

以 \(k = 3\) 为例

\[\begin{aligned}
\sum_{x=1}^1 &= a_1 \binom 22 + a_2 \binom 23 + a_3 \binom 24 = 1 \\
\sum_{x=1}^2 &= a_1 \binom 32 + a_2 \binom 33 + a_3 \binom 34 = 9 \\
\sum_{x=1}^3 &= a_1 \binom 42 + a_2 \binom 43 + a_3 \binom 44 = 36 \\
\end{aligned}
\]

同时我们规定 \(\binom nr = 0\ (n \lt r)\)。所以上式也可以写为

\[\begin{aligned}
\sum_{x=1}^1 &= a_1 \binom 22 &= 1 \\
\sum_{x=1}^2 &= a_1 \binom 32 + a_2 \binom 33 &= 9 \\
\sum_{x=1}^3 &= a_1 \binom 42 + a_2 \binom 43 + a_3 \binom 44 &= 36 \\
\end{aligned}
\]

这就是一个下三角矩阵，每一次扫一遍即可。

代码也非常简单，常数比第一种方法小很多：

void get_coefficient(int k, int * ccts) {
    int sum = 0;
    for (int n = 1; n <= k; ++n) {
        sum += qpow(n, k, MOD);

        int rest = sum;
        // 由于我们已经知道了前 (n-1) 个系数，直接通过总和一一减去即可。
        for (int i = 1; i < n; ++i) {
            // 注意 k < MOD，所以此处不需要Lucas
            (rest -= ccts[i] * C(n + 1, i + 1) % MOD) %= MOD;
        }
        if (rest < 0) rest += MOD;
        // 明显可知，C(n, n) = 1，所以剩下的即是系数
        ccts[n] = rest;
    }
}

核心部分也非常简单，只是模数较小，需要用到 \(Lucas\) 定理。

int ccts[K][K]; // 用于保存系数
void work() {
    int T, n, k;
    cin >> T;

    while (T--) {
        cin >> n >> k;

        int * cctk = ccts[k];
        if (!cctk[1]) // 其实不难发现，a1 一定为 1，所以借此判断即可
            get_coefficient(k, cctk);

        int ans = 0;
        for (int i = 1; i <= k; ++i)
            (ans += cctk[i] * Lucas(n + 1, i + 1)) %= MOD;
        cout << ans << '\n';
    }
}