K Sum 这个题名，我第一眼扫过去以为是道快速幂签到，读完题面才发现完全不是——它把一个看起来人畜无害的幂和求和，架在了一个大到不能枚举的 n 上，逼着你去回答一个问题：当求和项数到了十亿量级，你凭什么敢说自己算得对。真正把它做出来，靠的不是什么高深数论，而是把"求和"重新看成"多项式在某个点的取值"，再加上一份写得足够小心的拉格朗日插值模板。这篇文章我按当时复盘这道题的顺序走一遍：题面怎么翻译成能算的式子、幂和为什么必然是多项式、连续点插值的 (O(k)) 公式怎么推、代码里哪几行最容易翻车、以及这套模板之后还能怎么迁移。只要你会写快速幂、知道逆元是什么，下面的内容都能跟上；哪怕你只是刚接触插值，看完也能自己手推出那几行关键公式。

1. 先把题面翻译成能算的式子

1.1 题面里那句话到底在求什么

这道题在我手上的版本里，输入是 (n) 和 (k)，要求对 (10^9+7) 取模输出一个带权的幂和。题面绕了一层，写成双层求和的形式，看起来像是要枚举所有区间，但拆开之后本质非常朴素：对每个 (i)，(i^k) 贡献的次数等于包含 (i) 的区间个数。如果你把外层区间长度记作 (len)，内层起点记作 (l)，那么固定长度 (len) 时能取的起点有 (n-len+1) 个，于是整个和可以改写成

[ \sum_{len=1}^{n} (n-len+1)\cdot len^k ]

换成对指数底数求和，就是

[ \sum_{i=1}^{n} (n+1-i), i^k ]

到这一步，题面里所有"区间""子段"的壳子都被剥掉了，只剩下一个加权的自然数幂和。这个变形是我认为这道题第一个值得记住的地方：很多看起来需要数据结构维护的区间统计，只要权值和区间位置的关系是线性的，就能直接换成"每个元素被算了多少次"的视角，一次交换求和顺序，复杂度从平方级掉到线性级的思路雏形就出来了。

顺便说一句，题面里 (k) 的上界各个复现版本给得不太一致，我手上这份是在能枚举的范围内。下面的模板针对的就是"(k) 可以接受 (O(k)) 预处理"这个前提；如果哪天你遇到的版本把 (k) 也拉到了十亿级别，那说明题面里一定还有别的性质没被用上，第 5 节我会讲这种时候该往哪个方向想。

1.2 把加权和拆成两个纯幂和

上面那个式子还能再拆。把 ((n+1-i)) 拆成 ((n+1)) 和 (-i) 两部分，求和号分别作用：

[ \sum_{i=1}^{n} (n+1-i)i^k = (n+1)\sum_{i=1}^{n} i^k - \sum_{i=1}^{n} i^{k+1} ]

左边那个求和是我后面统一记作 (S_k(n)) 的东西，右边是 (S_{k+1}(n))。这个拆法的价值在于：它把一个带参数的求和，变成了两个标准形式的幂和，而标准的自然数幂和是有成熟处理套路的。如果你不拆，硬去插值原式，也不是不行，但次数判断和点值构造都会更啰嗦；拆开之后每个部分的形式统一，模板可以复用，调试的时候也能分开验证——先用小的 (n) 手算 (S_k(n)) 对不对，再看整体答案对不对，出错范围被压缩了一半。

这里有个细节值得提前记下来：拆出来的两个幂和次数不一样，(S_k(n)) 是 (n) 的 (k+1) 次多项式，(S_{k+1}(n)) 是 (n) 的 (k+2) 次多项式。也就是说你不能用同一张点值表插两次，必须分别构造。很多人第一次写的时候图省事，拿 (S_k) 的点值直接去插 (S_{k+1})，结果就是死活对不上，一行行查也查不出毛病，因为逻辑上就已经假定错了。

1.3 复杂度算账：为什么暴力一点机会都没有

(n) 到 (10^9) 这个量级，任何 (O(n)) 的写法都是送死。即便你只枚举到 (n)，每次再套一个快速幂 (O(\log k))，总复杂度是 (10^9 \times 30)，差着好几个数量级。有人会想，那我把 (i^k) 的递推关系利用起来，线性筛一下，是不是能压到 (O(n))？理论上是的，但 (10^9) 次循环本身在时限内就过不去，常数再小也没用。

所以这题从复杂度上就只剩一条路：想办法让计算的代价与 (n) 无关，只与 (k) 有关。插值恰好提供了这个可能——如果我们能证明待求的量是 (n) 的一个次数不高的多项式，那就可以只在小范围内求出若干个点值，再把这几个点"外推"到大的 (n) 上去。代价从 (O(n\log k)) 掉到 (O(k\log k))，当 (k) 在 (10^5) 量级时，这个量级是完全可以接受的。这就是整套解法成立的动机，不是什么奇技淫巧，纯粹是复杂度逼出来的唯一出路。

2. 为什么幂和是个多项式：插值的合法性来源

2.1 用差分算子一句话说清次数

插值不是随便找个函数就能插的，你得先证明待求的量确实是多项式，而且知道它的次数，否则取几个点纯粹是碰运气。(S_k(n)=\sum_{i=1}^{n} i^k) 是多项式这件事，用差分看最直接。

考虑一阶差分

[ \Delta S_k(n) = S_k(n)-S_k(n-1) = n^k ]

右边是 (n) 的 (k) 次多项式。而多项式有一个基本性质：(d) 次多项式做一次差分，次数降到 (d-1)；反过来，如果一个函数的差分是 (d-1) 次多项式，那这个函数本身就是 (d) 次多项式（差一个常数项，不影响次数）。套进来就是：(\Delta S_k(n)) 是 (k) 次，所以 (S_k(n)) 是 (k+1) 次。

这个结论可以用初等公式验证，验证完心里就有底了。(k=1) 时 (S_1(n)=n(n+1)/2)，展开是二次的，符合 (k+1=2)；(k=2) 时 (S_2(n)=n(n+1)(2n+1)/6)，三次，符合；(k=3) 时 (S_3(n)=[n(n+1)/2]^2)，四次，仍然符合。三条都对上了，说明这个次数判断不是巧合。

有了"次数是 (k+1)"这个事实，插值的合法性就成立了：一个次数不超过 (d) 的多项式，被它在 (d+1) 个互不相同的点上的取值唯一确定。取 (d+1=k+2) 个点，就能把 (S_k) 在整个数轴上"钉死"，包括我们需要的那个巨大的 (n)。

2.2 取点策略：为什么非得是连续的整数

理论上任意 (d+1) 个互不相同的点都能插值，但代价完全不同。标准的拉格朗日插值公式长这样：

[ f(x)=\sum_{i=0}^{d} y_i \prod_{j\neq i}\frac{x-j}{i-j} ]

如果点是随便选的，每个 (i) 对应的分母 (\prod_{j\neq i}(i-j)) 都得单独花 (O(d)) 算一遍，总共 (O(d^2))，对 (k=10^5) 来说就是 (10^{10})，直接超时。

但如果点取成 (0,1,2,\dots,d)，分母就有了闭式：

[ \prod_{j\neq i}(i-j)=\left(\prod_{j<i}(i-j)\right)\left(\prod_{j>i}(i-j)\right)=i!\cdot(-1)^{d-i}(d-i)! ]

前面是阶乘，后面是带符号的阶乘，都可以 (O(1)) 查表拿到。分子那部分 (\prod_{j\neq i}(x-j)) 也能预处理：把所有 ((x-j)) 乘起来记作总积，然后对每个 (i) 用总积除以 ((x-i)) 就行——但这里有除零风险，当 (x) 恰好落在取点范围内时 ((x-i)) 会变成 0，除法就崩了。所以工程上更常见的做法是前缀积和后缀积，见 3.2 节。

这一步的取舍非常典型：为了把 (O(d^2)) 压到 (O(d))，付出的代价是取点必须规整。而 (S_k(n)) 在 (0,1,\dots,k+1) 上的取值恰好可以递推着求出来，一点都不浪费，两边正好咬合上。

2.3 一个容易被忽略的合法性条件

还有个坑我不止一次见人踩：我们是在模 (10^9+7) 这个有限域里做插值的，阶乘逆元要求分母不能是模数的倍数。也就是说必须满足 (d < 10^9+7)。这道题 (k) 在 (10^5) 量级，(d=k+2) 远小于模数，安全。

但如果哪天你把模板拿去用在 (k) 接近模数的题上，这套东西是会静默出错的——阶乘算到模数那一项直接变成 0，逆元算不出来，结果是一堆看似正常的错误数字，非常难查。所以我在模板里习惯在预处理函数入口加一句断言或者注释，提醒自己上界必须在模数以下。这是那种"平时永远用不到，一旦用到能省你三个小时"的防御性写法。

3. 落地实现：从点值表到一次 AC

3.1 预处理阶乘逆元的上界要算准

先算清楚需要多大的表。求 (S_k(n)) 时 (d=k+1)，需要点 (0..k+1)，共 (k+2) 个，插值公式里会用到 (i!) 和 ((d-i)!)，最大是 (d!=(k+1)!)。求 (S_{k+1}(n)) 时 (d=k+2)，需要 ((k+2)!)。所以阶乘表的容量至少要到 (k+2)，我习惯直接开到 (k+5) 留点余量。

逆元的求法是先算 (fac[limit]) 的逆元，然后倒着推：

void init(int n) { fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i-1] * i % MOD; ifac[n] = pw(fac[n], MOD - 2); for (int i = n; i >= 1; i--) ifac[i-1] = (ll)ifac[i] * i % MOD; }

倒推那一步的道理是 (\frac{1}{(i-1)!}=\frac{i}{i!})，也就是用后一项的逆元乘上 (i) 得到前一项，一次 (O(1))，总共 (O(n))。这是常用做法，但要注意必须站在同一个上界上倒推——如果你 fac 算到 (k+2) 而 ifac 从 (k+5) 开始倒推，前几项会全错。这种错很隐蔽，因为大部分测试点用的是小 (k)，你看不出问题，直到某组数据卡在上界附近才炸。

3.2 前后缀积的边界与下标陷阱

插值主体这部分，我建议你把每个数组的定义写在草稿纸上，别凭记忆写。我用的是这一套：

• pre[i]表示 (\prod_{j=0}^{i-1}(n-j))，pre[0] = 1
• suf[i]表示 (\prod_{j=i}^{d}(n-j))，suf[d+1] = 1

那么"去掉第 (i) 项的乘积"就是pre[i] * suf[i+1]。注意suf的下标是i+1，不是i，这个地方错了会导致整体结果偏差极大但看起来又有模有样，很难通过对照小数据发现——因为小的 (n) 在特判分支里就走了，根本走不到这段代码。

pre[0] = 1; for (int i = 0; i <= d; i++) pre[i+1] = (ll)pre[i] * ((n - i) % MOD) % MOD; suf[d+1] = 1; for (int i = d; i >= 0; i--) suf[i] = (ll)suf[i+1] * ((n - i) % MOD) % MOD;

还有入口处那个判断：if (n <= d) return y[n];。理论上不写它，公式也能算对——因为分子里的 ((n-n)) 会让除了第 (n) 项之外的所有项自动变成 0，而第 (n) 项的分子分母恰好抵消。但我不建议省：省下来的是 (O(k)) 的常数，多出来的是理解和调试的成本，而且一旦 (n) 在传递过程中变成负数或者类型不对，这个地方会直接越界。工程上能提前掐掉的分支就提前掐掉，这是我写模板一贯的原则。

3.3 主函数里的组装

前面说过答案是 ((n+1)S_k(n)-S_{k+1}(n))，组装的时候注意两点：$(n+1)$ 要先对模数取余，减法要处理负数。

int sk = powerSum(n, k); int sk1 = powerSum(n, k + 1); ll ans = ((n + 1) % MOD * sk % MOD - sk1 + MOD) % MOD;

(n+1) % MOD * sk这一步容易溢出，因为中间乘积是 (10^{18}) 量级，必须用long long承接，或者强制转换一次。我见过有人直接写(n+1)*sk%MOD然后百思不得其解，其实是中间结果在 int 里就已经回绕了。

用 (n=2,k=2) 手算验证一下：((3)\times(1+4)-(1+8)=15-9=6)。直接按原始定义算，(i=1) 贡献 (1\times 2=2)，(i=2) 贡献 (4\times 1=4)，和是 6，对上了。每次改完代码我都习惯用这种"两条路算同一个数"的方式交叉验证，比盯着代码看有效得多。

3.4 完整代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1000000007; const int MAXN = 100005; int fac[MAXN], ifac[MAXN]; int pw(int a, int b) { int r = 1; a %= MOD; while (b) { if (b & 1) r = (ll)r * a % MOD; a = (ll)a * a % MOD; b >>= 1; } return r; } void init(int n) { fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i-1] * i % MOD; ifac[n] = pw(fac[n], MOD - 2); for (int i = n; i >= 1; i--) ifac[i-1] = (ll)ifac[i] * i % MOD; } // y[0..d] 为 f(0..d) 的取值，返回 f(n) int interpolate(const vector<int>& y, ll n) { int d = (int)y.size() - 1; if (n <= d) return y[(int)n]; vector<int> pre(d + 2), suf(d + 2); pre[0] = 1; for (int i = 0; i <= d; i++) pre[i+1] = (ll)pre[i] * ((n - i) % MOD) % MOD; suf[d+1] = 1; for (int i = d; i >= 0; i--) suf[i] = (ll)suf[i+1] * ((n - i) % MOD) % MOD; ll res = 0; for (int i = 0; i <= d; i++) { ll t = (ll)y[i] * pre[i] % MOD * suf[i+1] % MOD; t = t * ifac[i] % MOD * ifac[d-i] % MOD; if ((d - i) & 1) res -= t; else res += t; } res %= MOD; if (res < 0) res += MOD; return (int)res; } // 返回 sum_{i=1}^{n} i^k int powerSum(ll n, int k) { if (n == 0) return 0; int d = k + 1; // 多项式次数 vector<int> y(d + 1, 0); // 需要 d+1 个点: 0..d for (int i = 1; i <= d; i++) y[i] = (y[i-1] + pw(i, k)) % MOD; return interpolate(y, n); } int main() { int T; scanf("%d", &T); while (T--) { ll n; int k; scanf("%lld %d", &n, &k); init(k + 5); int sk = powerSum(n, k); int sk1 = powerSum(n, k + 1); ll ans = ((n + 1) % MOD * sk % MOD - sk1 + MOD) % MOD; printf("%lld\n", ans); } return 0; }

这段代码我建议你自己敲一遍，别复制。敲的过程中你会自然去想suf的下标为什么是i+1、d到底等于 (k+1) 还是 (k+2)，这些想明白了，模板才真正属于你。

4. 踩坑与排查实录

4.1 负数取模：最经典也最容易复发

插值公式里那一项 $(-1)^{d-i}$，实现时是if ((d-i)&1) res -= t; else res += t;。如果只在循环结束后做一次%MOD，res有可能是个负数。C++ 的取模对负数保留符号，所以res % MOD仍然是负数，输出就会变成-123456789这种。

我当时的修法是两步：先res %= MOD，再if (res < 0) res += MOD;。注意只加一次 MOD 就够了，因为 (d+1) 项累加的值域已经被前一步的取模压到了 $(-MOD, MOD)$ 区间内。但如果你在循环里没有对res做任何约束，累加的值可能超出long long，那时候加一次 MOD 也救不回来，得在循环内就控制住。

4.2 次数搞错：最容易被忽略的错

有一类错误的表现是"小数据全对，大数据全错"。我遇到过最常见的原因是把 (S_{k+1}) 的次数当成了 (k+1)。因为写顺手了，两处都传k+1，结果 (S_{k+1}) 少取了一个点，插出来的多项式次数不够，在小 (n) 上因为点值直接命中所以看不出问题，一到大 (n) 就整体偏移。

排查方法很土但有效：写一个 (n) 从 1 到 200 的暴力版本，和你的插值版本逐个比对。如果前半段全对、后半段开始偏，那基本可以断定是次数或者点值数量的问题。这个对拍脚本我几乎每道用到插值的题都会写一份，五分钟的事，能省几个小时。

4.3 上界开小导致的越界

init(k + 5)这句，如果某组数据的 (k) 超过了你数组开的大小，越界写会静默改掉旁边的变量，现象是"有时候对有时候不对"，非常邪门。我自己的习惯是数组开到MAXN，然后在init里加一句if (n >= MAXN) n = MAXN - 1;之外的防御——更好的办法是直接用vector动态开，虽然稍微慢一点，但绝对不会错。

另外一个相关的坑是多组数据之间没有清空。这道题每组数据的 (k) 不一样，阶乘表要重算。如果图快只在第一组算一次，后面组的数据就会错。我的写法是每组都调用init，代价是每组 (O(k))，在 (k=10^5)、(T) 不大的情况下完全可以接受。真到了 (T) 很大的场景，就得改成按最大 (k) 预处理一次，那是另一个话题了。

4.4 速查表

5. 模板迁移：这类题还能怎么变

5.1 带权幂和的几种常见形态

把这道题抽象一下，你手里其实攒下了一个能处理"(\sum i^k \cdot P(i))"的框架，其中 (P) 是低次多项式。比如 (\sum i^k \cdot i) 就是 (\sum i^{k+1})，直接降级成标准幂和；(\sum i^k (a-i)) 是线性加权，拆成两个幂和；再复杂一点像 (\sum i^k \cdot i^2)，那就变成 (k+2) 次幂和，次数往上加就是了。

真正的难点在于权值不是多项式的情形，比如权值是 (2^i) 或者组合数。这时候插值就不适用了，得换别的思路，比如构造递推或者用生成函数。我一般的判断标准是：如果权值本身能写成关于 (i) 的多项式，就拆；如果带指数或者阶乘，就老老实实回去找递推关系。

5.2 合并两次插值的思路

前面是分别插了 (S_k) 和 (