聚焦：无所畏惧的求和题解

2023-03-31 18:15:16 来源：博客园

无所畏惧的求和题解

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

(相关资料图)
可能可以评一个黑？可能有点过，但是紫色是肯定可以的。
题目链接：无所畏惧的求和 - 洛谷
尽情享受吧！

这道题其实做法有很多：

待定系数法 + 矩阵求解推代数公式
组合数学 + 待定系数法推组合公式
第一类斯特林数（时间复杂度可能有点问题，为 \(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";    }}

关键词：