幂和这类东西从入门时算 12…n到后来算 1^k2^k…n^k几乎是每个打竞赛的人都绕不开的老朋友。2019ICPC南京网络赛E题 K Sum 就把它玩出了点花样题面套了一层对每个区间求幂和再把所有区间加起来的壳子暴力写下去必挂但只要把求和号换个顺序整个式子会瞬间塌缩成两个幂和相减。而幂和本身又是关于 n 的多项式拉格朗日插值上来就是 O(k) 一次查询。这道题真正的分水岭不在代码长度而在两件事敢不敢先把三重求和化简到底以及插值那几行符号和阶乘逆元能不能一次写对。下面我按自己做这道题时的思路顺序把化简、插值原理、代码落地、踩坑排查完整走一遍适合已经会写快速幂和基础取模、但插值还没真正写熟的人看。1. 把题面翻译成人话那三层求和到底在数什么1.1 题意还原与符号约定题目先定义了一个区间幂和 g(l, r, k)意思是 l^k (l1)^k … r^k也就是对区间 [l, r] 里每个整数的 k 次幂求和。然后在这个基础上定义 f(n, k)把所有满足 1 ≤ l ≤ r ≤ n 的区间的 g 值全加起来。要求输出 f(n, k) 对 1e97 取模的结果。n 给得很大能到 1e9 这一档所以任何 O(n) 的循环都不能出现k 表面上也给了不小的上限但后面会看到插值做法的复杂度直接就是 O(k)所以 k 的量级决定了这条路走不走得通。这里先把符号钉死免得后面看代码时对不上S_m(n) 表示 Σ_{i1}^{n} i^m也就是从 1 到 n 的 m 次幂和。注意这个 S 是对 i 求和m 是幂次别和题目里的 k 搞混。后面所有推导都会落到 S_{k1}(n) 和 S_{k2}(n) 这两个量上。1.2 换一种眼光每个 i^k 被加了几次直接按题面写是三层循环外层枚举 l中层枚举 r内层再枚举 i 累加幂。这个写法的时间复杂度是 O(n^3) 级别n 1e9 的时候连编译都嫌它占地方。真正的破局点在于换一个视角不要去数每个区间贡献多少而要去数每个 i^k 到底被算进了多少个区间。固定一个 i问有多少对 (l, r) 满足 l ≤ i ≤ r。l 的取值范围是 1 到 i一共 i 种选法r 的取值范围是 i 到 n一共 n - i 1 种选法。这两个选择互相独立因为 l 只受左端点约束r 只受右端点约束所以总方案数就是 i × (n - i 1)。于是整个 f(n, k) 可以直接改写成 Σ_{i1}^{n} i^k · i · (n - i 1)。原来三层求和现在只剩一层而且这一层还不是普通的求和是带幂次的加权求和形式上已经很接近幂和了。1.3 从加权和到两个幂和相减把 i × (n - i 1) 展开得到 (n1)i - i^2。代回去f(n, k) Σ_{i1}^{n} i^k · [(n1)i - i^2] (n1) · Σ_{i1}^{n} i^{k1} - Σ_{i1}^{n} i^{k2}用人话说就是f(n, k) (n1) · S_{k1}(n) - S_{k2}(n)。到这一步题目的全部难点就只剩怎么快速算幂和了。这个化简不是巧合它是竞赛里非常通用的一类手法——凡是出现先枚举区间、再对区间内部做某种统计的结构都应该本能地想想能不能翻成枚举元素、统计它被多少个区间包含。前者天然是平方或立方级别后者往往是一层循环加一点组合计数。我对这个套路有个比较实用的判断标准如果内层统计的是和这种可加的量那就一定能翻如果内层统计的是最大值最小值不同元素个数这类不可加的量翻的时候就得换别的数据结构或者单调栈之类的工具。这道题属于前者翻得干干净净。1.4 别跳过手算验证这一步化简完之后我习惯拿小数据验一遍这一步看起来浪费时间实际上能省掉后面几十分钟的调试。取 n 2、k 1老老实实枚举区间 [1,1] 的幂和是 1[1,2] 是 12 3[2,2] 是 2加起来 6。用公式算(n1)·S_2(2) - S_3(2) 3 × (14) - (18) 15 - 9 6对上了。再取 n 2、k 2区间 [1,1] 是 1[1,2] 是 14 5[2,2] 是 4总共 10。公式这边是 3 × S_3(2) - S_4(2) 3 × (18) - (116) 27 - 17 10也对上了。再换 n 3、k 1三个左端点分别贡献 10、7、3总和 20。公式是 4 × S_2(3) - S_3(3) 4 × 14 - 36 56 - 36 20。三组数据都吻合这个化简就可以放心用了。我个人的习惯是至少验三组且其中有一组要满足 n ≥ 3、k ≥ 2这样能同时覆盖展开项和幂次错位这两类错误。2. 幂和为什么能插值把多项式这条路走通2.1 用差分证明 S_k(n) 的次数很多人知道幂和是多项式这个结论但说不清为什么遇到需要确定次数的时候就会卡住。最干净的证法是用差分。考虑 S_k(n) 的前后两项之差S_k(n) - S_k(n-1) n^k。也就是说S_k 这个函数的差分恰好是一个 k 次多项式。而差分算子会把多项式的次数降 1。反过来推如果差分之后是 k 次那原来就应该是 k1 次准确说是 k1 次多项式没有更高项因为差分把最高次项消掉的机制不成立——这里可以再细想如果原来是 k2 次差分后最高次仍在是 k1 次与已知矛盾。所以 S_k(n) 一定可以写成关于 n 的 k1 次多项式并且常数项为 0因为 S_k(0) 0。这条结论直接决定了我们后面要准备多少个点一个 d 次多项式需要 d1 个点才能唯一确定所以 S_{k1}(n) 是 k2 次需要 k3 个点S_{k2}(n) 是 k3 次需要 k4 个点。两个量放在一起最多准备到 k4 个点就够用了。2.2 拉格朗日插值的原始形式给定 d1 个互不相同的点 (x_0, y_0), …, (x_d, y_d)过这些点的 d 次多项式唯一并且可以写成F(x) Σ_{i0}^{d} y_i · Π_{j≠i} (x - x_j) / (x_i - x_j)这个式子的构造思路很直白对于第 i 项它的分子在 x x_i 时等于 Π_{j≠i}(x_i - x_j)正好被分母约掉值是 y_i而当 x 取到任何一个别的 x_t 时分子里含有 (x - x_t) 这个因子整个项变成 0。所以每一项都像是在说我只有在 x 等于我的点时才说话加起来就精确穿过所有点。一般写法要做 O(d^2) 的乘除但这里有个巨大的便利我们选择的取值点是连续整数。2.3 连续整数点带来的 O(d) 化简取 x_i ii 从 1 到 m其中 m 是点数。这时候分母 Π_{j≠i}(i - j) 变成一个非常规整的式子先看 j i 的部分乘积是 (i-1)!再看 j i 的部分乘积是 (i-(i1))·(i-(i2))·…·(i-m) (-1)^{m-i} · (m-i)!。合起来分母等于 (i-1)! · (m-i)! · (-1)^{m-i}。分子 Π_{j≠i}(x - j) 可以拆成两段前一段是 Π_{j1}^{i-1}(x - j)后一段是 Π_{ji1}^{m}(x - j)。如果把整个 Π_{j1}^{m}(x - j) 记作一个整体那么分子就等于它除以 (x - i)。所以只要预处理前缀积 pre[i] Π_{j1}^{i}(x-j) 和后缀积 suf[i] Π_{ji}^{m}(x-j)第 i 项的分子就是 pre[i-1] · suf[i1]O(1) 就能取到。于是整个求值过程变成先 O(m) 算 pre 和 suf再 O(m) 遍历一遍累加总复杂度 O(m)。配合前面说的m 等于 k4 这个量级整道题的复杂度就是 O(k)非常轻。2.4 那个 (-1) 到底是哪来的符号项是这道题最容易写错的地方我自己第一遍就把它写反了样例能过、随机数据全挂。把推导摊开看分母里 j i 的部分是 (i - (i1)) · (i - (i2)) · … · (i - m)每一项都是负数一共有 m - i 项所以贡献了 (-1)^{m-i}。放到倒数里1/分母 (-1)^{m-i} / [(i-1)! · (m-i)!]。因为 (-1) 的倒数还是它自己符号不变。所以在代码里第 i 项的系数就是 y_i · pre[i-1] · suf[i1] · ifac[i-1] · ifac[m-i]然后再看 (m - i) 的奇偶决定加还是减。一个小技巧与其写 if 判断再取负不如直接在累加时用if ((m-i) 1) term (MOD - term) % MOD;这样负数被自动归一到 [0, MOD) 区间避免后面再处理负余数。这个细节在多组数据里尤其重要因为一次负余数残留就可能污染整轮答案。2.5 特判x 落在已知点上要直接返回还有一个非常关键的特判。如果要求值的 x 本身就在 1 到 m 之间那它已经是我们预处理过的点直接返回对应 y 值就行。虽然理论上公式也能算出正确结果分子分母在 i x 那项会正常约掉其他项因为含 (x - x_j) 0 而归零但数值上要做一堆无谓的乘除还容易在 (x - i) 为 0 时踩到除零的坑虽然我们的写法不显式除但 pre 和 suf 里会出现 0某些项变成 0边界处理不干净时容易出错。更重要的是性能多组数据、每组都要问一次能省一次 O(k) 就省一次。顺带提一句一个更隐蔽的坑如果 n 的值域能超过模数那么 (x - i) 取模之后可能落回 1..m 里导致本来不为零的项被人为清零。这道题 n 最大 1e9小于模数 1e97所以不会触发但如果以后遇到 n 达到 1e18 的变种就必须把 x 先对模数取模再参与运算同时还要单独记录 x 是否真的落在点集里。这个坑我在别的题上真踩过调了很久才反应过来。3. 代码落地从预处理到查询的完整实现3.1 整体框架与技术选型整份代码分四块快速幂、阶乘与阶乘逆元预处理、拉格朗日插值求值、主逻辑组装答案。选 C 是因为 k 到 1e5 这个量级时O(k) 的数组操作和取模运算在常数上比别的语言稳多组数据累计起来差距会很明显。数组开多大取决于题目给的 k 上限。如果 k 在 1e3 这一档开到 5000 绰绰有余如果 k 能到 1e5就开到 1e520。我的习惯是直接按上限的 1.1 倍再留点富余比如const int MAXK 100000 20;因为插值过程里会用到 k4 这个下标边界少留一点就可能越界而且这种越界在本地小数据上根本看不出来。3.2 阶乘与阶乘逆元的预处理阶乘逆元用一次费马小定理求最大值再倒推。这一步是标准的#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1000000007LL; ll qpow(ll a, ll b) { ll r 1; a % MOD; while (b 0) { if (b 1) r r * a % MOD; a a * a % MOD; b 1; } return r; } vectorll fac, ifac; void init_fac(int n) { fac.assign(n 1, 1); ifac.assign(n 1, 1); for (int i 1; i n; i) fac[i] fac[i-1] * i % MOD; ifac[n] qpow(fac[n], MOD - 2); for (int i n; i 1; i--) ifac[i-1] ifac[i] * i % MOD; }这里有个细节值得说一下init_fac里传的 n 必须是至少 k4而不是 k。原因前面推过S_{k2} 需要 k4 个点插值公式里要用到 ifac[m-i]m 最大取到 k4所以 ifac 的下标要能到 k4。我见过有人写成init_fac(k)本地测 k 1 的小数据完全正常一到 k 大的点就数组越界输出一堆随机数。3.3 插值函数逐行拆解// y[1..m] 是 f(1..m) 的值f 为 m-1 次多项式求 f(x) ll lagrange(const vectorll y, ll x, int m) { if (x 1 x m) return y[(int)x]; vectorll pre(m 2, 1), suf(m 2, 1); for (int i 1; i m; i) { ll t ((x - i) % MOD MOD) % MOD; pre[i] pre[i-1] * t % MOD; } for (int i m; i 1; i--) { ll t ((x - i) % MOD MOD) % MOD; suf[i] suf[i1] * t % MOD; } ll res 0; for (int i 1; i m; i) { ll term y[i] * pre[i-1] % MOD * suf[i1] % MOD; term term * ifac[i-1] % MOD * ifac[m-i] % MOD; if ((m - i) 1) term (MOD - term) % MOD; res (res term) % MOD; } return res; }pre[i]的定义是 Π_{j1}^{i}(x - j)suf[i]的定义是 Π_{ji}^{m}(x - j)两者相乘再除掉 (x - i) 就是分子。因为代码里不显式除直接用 pre[i-1] 和 suf[i1] 拼就绕开了除法。这个写法的好处是即使 x 恰好等于某个 j也不会出现除以零。取模那里的((x - i) % MOD MOD) % MOD是防御性写法。这道题里 x n 最大 1e9i 最大也就 k4正常情况下 x ≥ i 只在 x 落在点集内时才发生而这个情况已经被前面的 if 拦掉了所以实际不会出现负数。但如果哪天换成 n 可以很小的输入或者换一道题复用这个函数这段防御就能救命。养成习惯比临时判断划算。3.4 主逻辑与幂的批量计算优化主函数里要做的事先算两个前缀和数组再做两次插值最后组答案。int main() { int T; scanf(%d, T); while (T--) { ll n, k; scanf(%lld %lld, n, k); int M (int)(k 4); init_fac(M 1); vectorll y1(M 1, 0), y2(M 1, 0); for (int i 1; i M; i) { ll p qpow(i, k 1); // i^(k1) y1[i] (y1[i-1] p) % MOD; // S_{k1}(i) y2[i] (y2[i-1] p * i) % MOD; // i^(k1) * i i^(k2) } ll S1 lagrange(y1, n, M - 1); // k3 个点 ll S2 lagrange(y2, n, M); // k4 个点 ll ans (((n 1) % MOD) * S1 % MOD - S2 % MOD MOD) % MOD; printf(%lld\n, ans); } return 0; }这里有个很值的优化i^{k2} 不需要再算一次快速幂它等于 i^{k1} 乘以 i。每个 i 只做一次 O(log k) 的幂运算总复杂度从 2k·log k 降到 k·log k虽然渐进复杂度没变但常数直接减半。k 到 1e5 这个量级、多组数据叠起来的时候这个改动能让运行时间从紧张变成宽松。还有一个细节(n 1) % MOD这个取模不能省。n 最大 1e9n1 在 long long 范围内没问题但如果你用 int 存 nn 1 就可能溢出到负数。用 long long 存输入、并且在乘之前取模是个不假思索就能写上的保险。3.5 为什么两个插值用的点数不一样这一点值得单独拎出来讲因为它是很多人写错的地方。S_{k1}(n) 是 k2 次多项式理论上需要 k3 个点S_{k2}(n) 是 k3 次多项式需要 k4 个点。如果图省事两个都传 M k4会不会错不会错但会浪费。因为多项式的次数是确定的多给一个点只是让插值公式里多算一项而那一项的系数恰好为 0因为多出来的点也满足那个更低次的多项式关系。所以两个都传 k4 是安全的只是白算一项。反过来如果两个都传得比真实点数少那就一定错算出来的多项式根本不过那些点。我在代码里传 M-1 k3 给 S1传 M k4 给 S2是在正确和效率之间取了个平衡。你要嫌麻烦两个都传 M 完全没问题。3.6 复杂度与空间核算时间复杂度每组数据 O(k log k)幂运算主导插值部分 O(k)总的就是 O(k log k)。空间上两个 y 数组加两个 pre/suf 数组都是 O(k)k 1e5 时也就几 MB毫无压力。如果题目是多组数据且 k 的上限固定更好的做法是把 fac、ifac 和 pre、suf 都提到全局每个测试点只初始化一次避免反复 assign 造成的内存抖动。我实测过T 比较大的时候这个改动能带来肉眼可见的提速。4. 实战踩坑那些让你 WA 到怀疑人生的细节4.1 k 的量级是这条路能不能走的前提这是必须先说清楚的一点。插值做法的复杂度是 O(k)所以它成立的前提是 k 本身不大。这道题能这么解本质上是因为 k 的量级控制在 1e3 到 1e5 这一档而 n 可以到 1e9。如果哪天你遇到 k 也到 1e9 的版本这套
