这周的牛客周赛 Round 135 打下来最让我有记录欲望的不是榜一大哥那几道压轴题而是全场通过率最高的那道“区间次方和”。它看起来平平无奇连搜索热词里都单独挂上了“区间次方和”这个名头说明不少人在赛后被这道题卡过思路——或者说卡在了“为什么我写的线段树TLE了”这个灵魂拷问上。我早年打周赛也是这个毛病看到区间查询就条件反射上线段树结果数据一大就吃瘪。这篇文章就把 Round 135 里这道区间次方和题目从头到尾拆一遍题意怎么还原、暴力错在哪、二维前缀表是怎么一步步推出来的、代码里有哪些容易被评测机判罚的细节最后再聊聊这道题往深了能延伸出哪些变体。无论你是刚开始打周赛的新人还是想找思路兜底的老人这轮复盘应该都能给你一点东西。1. 赛前摸底Round 135 的题量、节奏和这题的定位1.1 牛客周赛的常规节奏牛客周赛这几年我基本没断过赛制也摸得很清了。一般就是一次周赛五道题左右比赛窗口两个小时题目难度呈阶梯状往上铺前面一两道是签到题看懂了就能写中间一两道需要一点思路转换最后压轴的基本是那种“想通了一百行搞定、想不通一个半小时白给”的题。Round 135 的整场节奏也大体如此但这次有个很有意思的现象往后压轴的题卡住了不少人反而是中间这道“区间次方和”成了全场热度最高的讨论点。原因倒不是它多难而是它的解法一旦选错代码写起来会很顺手但运行起来就非常难受——这种“看起来像套模板、实际上需要换个思路”的题恰恰是周赛里最容易拉开差距的地方。1.2 五道题的难度分布与策略取舍我打周赛的固定策略是先花五分钟把五道题全部扫一遍根据题型和通过人数预判难度然后再决定动手顺序。Round 135 这次的整体分布大概是这样的第一题模拟题注意边界条件就能过属于热身题。第二题稍微带点贪心或者双指针难度不大。第三题区间次方和看着很“数据结构”实际是个前缀和的套路题也是这次文章的主角。第四题需要一点数论或组合数学的底子开始有人掉队。第五题压轴题涉及比较复杂的维护逻辑大部分人的时间都耗在这。如果你一上来就扎进最后一题很可能前三题都没时间好好拿分。我的建议是先保证前四题稳定拿分最后一题有多余时间再攻。区间次方和这道题因为处在第三题的位置难度决定了它必然有一套“短平快”的正解如果你在这里写出了一个又长又慢的线段树那就已经走偏了。1.3 为什么“区间次方和”这个热词能挂上榜单赛后逛了一圈讨论区发现“区间次方和”被反复提起不是因为这题解法高深而是它勾出了两类典型错误一类是没看数据范围直接对每个查询暴力遍历区间另一类是看到“区间”就写线段树结果更新和查询都有问题。这两类人在赛后的共同感受都是——我怎么就没想到前缀和。说到底区间查询类问题里“前缀和”和“线段树”是一对需要分清的选项前者处理的是静态数组的某种可减可加的区间聚合后者处理的是动态更新和复杂聚合。Round 135 这题的数据是静态的、查询也不带修改所以前缀和才是那套最匹配的方案线段树属于杀鸡用了牛刀。2. 区间次方和题意还原与暴力解法的天花板2.1 完整题目描述还原先说清楚这题到底在问什么。基于 Round 135 的赛题内容和赛后讨论我把它完整还原成下面这个形式如果你手头正好有原题可以对照着看给定一个长度为 n 的数组 a下标从 1 开始。有 q 次查询每次查询给出三个参数 l, r, p你需要输出这个区间内所有元素的 p 次方之和sum_{il}^r a[i]^p所有结果要对 1e97 取模。数据范围大概是 n、q 都在 10^5 这个量级数组元素 a[i] 最大可以到 1e9而 p 的取值范围是关键——它在 1 到 5 之间非常小。这个“p 在 1 到 5 之间”可不是乱写的它就是整个题目的命门。很多人在赛桌上没注意到 p 的范围或者注意到了但没往心里去。这里我提前划个重点当你看到一个区间查询题目的某个参数范围特别小比如 p 只有 1 到 5那就意味着我们可以对每个可能的 p 分别维护一份前缀信息。数据结构题里的“小范围参数”往往就是出题人留给你的钥匙。2.2 直接模拟的复杂度估算拿到题的一瞬间最自然的写法就是每次查询遍历一遍区间对每个元素做快速幂累加取模。伪代码大概长这样for (int i l; i r; i) { ans (ans fast_pow(a[i], p, MOD)) % MOD; }看着没毛病但你得算一笔账。单次查询的复杂度是区间长度乘以快速幂的 O(log p)。q 次查询在最坏情况下可能每次都要查接近整个数组也就是每次查询遍历接近 n 个数。那么总复杂度大约是O(q * n * log p)把 n 10^5、q 10^5、log p 当作常数来算这是 10^10 量级的运算。评测机每秒大概能跑 10^7 到 10^8 次简单操作也就是说理论上要跑到 100 秒以上TLE 是板上钉钉的。如果你用了时间复杂度更高的实现比如每次查询里再嵌套一个复杂度更高的运算那只会死得更快。所以第一步结论很明确任何“每次查询都单独算一遍区间内的元素”的思路都不可能在 10^5 的数据范围下过关。2.3 为什么线段树在这题里不是最优解接下来就得说说不少人的第二反应——线段树。这个反应太正常了因为整个算法学习体系里“区间查询”这个词几乎就是和线段树绑定的。但大家要记住一个前提线段树的强项是支持“动态修改 区间查询”而它的代价是每次操作都要 O(log n) 向下递归常数还不小。也就是说单次查询 O(log n) 的复杂度在 q 10^5 的情况下其实是能过的问题不在这里。真正的问题出在“次方和”这个聚合方式上。线段树合并子区间的信息依赖的是一个可以快速合并的“结合律”。对于普通的区间和两个子区间的和相加就是父亲的和没问题。但对于区间次方和如果题目要求你支持修改某个区间的值比如把区间内所有元素统一加上一个偏移量 c那么你要面对的就是 (x c)^p 的展开其中牵扯到二项式展开旧的 p 次方和不能直接推导出新的 p 次方值。除非你同时维护 0 次方、1 次方、2 次方……一直到 p 次方的高阶矩才能实现 O(p^2) 的合并复杂度会随 p 上升得很厉害而且写起来极易出错。再说 Round 135 这题根本没有修改操作数组是静态的查询是纯读操作。对纯静态的区间查询线段树能做的前缀和往往能做得更好。那为什么很多人还是一眼写线段树惯性思维。做题最怕的不是不会而是会用一套“万金油”招数去套所有题结果在简单题上反而花掉了大量时间。3. 正解推导从“次方很小”这个约束走到二维前缀表3.1 核心观察p 的取值范围是突破口来把正解从头推一遍。这题最关键的一句话我已经反复强调了p 只有 1 到 5。这意味着查询虽然叫“区间次方和”但事实上任意一次查询的次方参数只会落进 5 个可能值里。既然这样我们就可以把一个大问题拆成 5 个子问题区间内所有元素的 1 次方和也就是普通的区间和区间内所有元素的 2 次方和区间内所有元素的 3 次方和区间内所有元素的 4 次方和区间内所有元素的 5 次方和每一个子问题单独看都是一个标准的“静态数组区间求和”问题而静态数组区间求和的标准解法就是前缀和。如果有 5 个子问题那我们就准备 5 张前缀和表查询的时候根据 p 的值选对应那张表然后用前缀和的经典减法公式 O(1) 出答案。这个思路的本质上是一种维度拆解把“次方参数 p”这个维度从查询里提出来做成索引维度。很多区间题看起来复杂其实就是因为多个维度纠缠在一起。你只要找出一个取值范围极小、可枚举的维度把它拆出来作为一部分预处理空间剩下的部分往往就变得平平无奇了。这类思想在算法题里非常常见二维前缀、三维前缀也是同源的思路。3.2 预处理表的构造细节具体到实现我们需要一张二维表行对应次方数 p0 到 5共 6 行列对应数组位置 i1 到 n。表中每个格子 pre[p][i] 的含义是从数组第 1 个元素到第 i 个元素的 p 次方之和且对 MOD 取模。换句话说pre[p][i] (pre[p][i-1] a[i]^p) % MOD构造过程是两重循环外层遍历 p内层遍历数组下标 i每次只需要做一次快速幂、一次加法和一次取模总复杂度 O(P * n * log p)其中 P 是 5。算一下数5 * 10^5 * 3也就是大约 150 万次运算对评测机来说就是一眨眼的事。写代码的时候要注意一个习惯问题数组下标尽量从 1 开始让 pre[p][0] 0 作为天然边界。这样在查询时用减法公式不会出现“下标为负”的情况逻辑上更顺。很多人习惯从 0 开始遍历数组结果写查询的时候就得各种凑下标不但容易写错调试也麻烦。3.3 查询公式与正确性证明有了 pre 表查询就非常干净了。对于一次查询 (l, r, p)答案直接用这一行两个位置的前缀和相减ans (pre[p][r] - pre[p][l-1]) % MOD之所以敢这么做是因为我们维护的“次方和”满足减法性质——前缀和的本质是累积而累积可以“撤销”。我从 l 到 r 的和等于前 r 项的和减去前 l-1 项的和剩下的就是第 l 项到第 r 项的部分。这在数学上等价于“把区间外的那部分贡献扣掉”非常直接。但这里有个所有新手都会踩的坑取模减法在 C 里可能得到负数。因为 pre 里存的是模意义下的值如果 pre[p][l-1] 大于 pre[p][r]相减得到的 ans 就是负的直接输出就 WA 了。所以每次减法之后必须做一次修正ans (pre[p][r] - pre[p][l-1] MOD) % MOD;先加上一个 MOD 再取模就可以保证结果归到 [0, MOD) 区间内。这不仅仅是为了这题的通过所有“前缀和减法取模”的问题都必须养成这个习惯。你可以在草稿纸上自己推理一下pre[p][r] 和 pre[p][l-1] 都在 [0, MOD) 内两者相减的取值在 (-MOD, MOD) 之间加一个 MOD 之后就落在 (0, 2*MOD) 内再取模就是正确结果。4. 完整代码与取模、卡常这些容易翻车的细节4.1 可直接提交的 C 代码下面是我赛后整理出来的一版完整可提交的 C 实现。注释写得比较细主要目的是让你看清每一步在干什么#include bits/stdc.h using namespace std; using ll long long; const ll MOD 1e9 7; const int MAXP 5; ll fast_pow(ll base, ll exp, ll mod) { base % mod; ll res 1; while (exp 0) { if (exp 1) res res * base % mod; base base * base % mod; exp 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorll a(n 1); for (int i 1; i n; i) { cin a[i]; } // pre[p][i] 表示前 i 个元素的 p 次方和p 从 1 到 5 vectorvectorll pre(MAXP 1, vectorll(n 1, 0)); for (int p 1; p MAXP; p) { for (int i 1; i n; i) { ll val fast_pow(a[i], p, MOD); pre[p][i] (pre[p][i-1] val) % MOD; } } while (q--) { int l, r, p; cin l r p; // 如果 p 超出 1~5 的范围说明题目数据不止一种情况需要额外处理 if (p 1 || p MAXP) { // 这里通常是预留扩展Round 135 中 p 始终在 1~5 内 } ll ans (pre[p][r] - pre[p][l-1] MOD) % MOD; cout ans \n; } return 0; }核心不到 40 行去掉输入输出就更短了。这就是“短平快”的典型代表也是评测机上最稳定的写法。如果你在赛场上写出了比这个复杂得多的结构请停下来想一想——是不是哪一步思路跑偏了。4.2 快速幂里的溢出陷阱可能有人会说p 最大只有 5为什么要写快速幂直接用一个 for 循环乘 5 次不就行了。确实可以而且更快。但我写 fast_pow 有一个原因它天然处理了中途乘法溢出的问题。关键在 a[i] 的最大值可以达到 1e9。你算 a[i]^5 的时候如果直接用朴素乘法算完再取模中间结果是 1e9 的 5 次方也就是 1e45 级别早就超出了 long long 的表示范围会发生溢出结果完全乱掉。所以每做一次乘法都必须立刻对 MOD 取模快速幂的内部本身就是每一步 mod 的能保证中途数字始终在 long long 范围内。当然因为 p 很小你也可以不写快速幂而直接用循环累乘效果一样代码可能更容易被新手看懂ll val 1; for (int k 0; k p; k) { val val * a[i] % MOD; }这个写法在 p 只有 1 到 5 时完全OK且不引入任何额外的复杂度。实战里怎么顺手怎么来关键是“每步取模”这个纪律要守住。4.3 读入优化与内存布局这题读入量是 n 3qn 和 q 都在 1e5 量级总共不到 40 万次整数读入用 cin 加加速配置是完全可以过的。我上面代码里已经写了ios::sync_with_stdio(false); cin.tie(nullptr);这两行是 C 选手的肌肉记忆。不写的话cin 每次读入都要和 C 标准输入输出同步会慢上一个量级。每次周赛我都看到有人因为忘写这两行被卡掉不少分真的是最冤的丢分方式。内存方面pre 表是 (51) * (n1) 个 long long大约是 6 * 1e5 * 8 字节 4.8 MB完全没有压力。如果你用 int 存可能会有溢出风险建议直接开 long long省心。4.4 一个容易被忽略的边界p0 的情况虽然 Round 135 这题我看到的版本 p 是从 1 到 5但很多类似题会在某个测试点偷偷放 p0。按数学约定任何数的 0 次方都等于 1包括 0 的 0 次方在某些编程语言里也返回 1。也就是说如果查询参数 p 等于 0答案就是区间长度 r - l 1连数组里的数长什么样都不需要管。如果你在赛场上遇到 p0 的情况最稳的处理是把它单独判掉if (p 0) { cout (r - l 1) % MOD \n; continue; }如果你不加这个判断直接用快速幂去算 a[i]^0大部分实现也会得到 1结果说不定也是对的。但明确写出来既免疫了语言差异也让读代码的人一眼就看懂你的意图。5. 赛后的延伸思考变体与下一步5.1 换作区间连乘还能不能用前缀和打比赛最大的收获不只是会做这一道题而是把一道题吃透之后能秒掉一片同类题。赛后我习惯性地把“区间次方和”往周边变体上想了一遍第一个想到的就是“区间连乘”。给定一个静态数组多次查询区间内所有元素的乘积要取模。这个问题能不能用前缀和思路不能直接用前缀和做除法式的撤销因为当模数是素数时可以用乘法逆元prod(l, r) prefix_prod[r] * inv(prefix_prod[l-1]) % MOD其中 prefix_prod[i] 表示前 i 个数的乘积取模inv 表示模 MOD 下的乘法逆元。这和前缀和的减法对应本质上也是一种“累积信息、差分撤销”的思想。如果你把这道区间次方和完全吃透了这个变体对你来说也就是几分钟的事。5.2 如果 p 的范围不再受限前缀表会失效吗这是评论区里问得最多的问题。如果把 p 的范围扩大到 1e5甚至每次查询的 p 都不同那我们的 5 行前缀表就直接失效了因为你不能为 1e5 种情况各建一张表。那怎么办首先想清楚p 既然很大就不可能用 O(1) 查询直接出答案复杂度需要重新平衡。一个常见套路是离线处理把所有查询按 p 排序离线操作。对于相同的 p可以一次性建立这组查询要用的次方数组例如先对数组里所有元素求 p 次方再做一次前缀和然后统一回答所有 p 相同的查询。这样复杂度是“不同的 p 的种数”乘以“n”如果不同 p 的数量是 m总复杂度大约是 O(m * n q)。当 m 小于 1e5 量级时这仍然是可接受的。更进一步还可以用莫队来维护每种次方的桶代价是复杂度更高思路也更绕。这种“静态区间 查询参数变化”的问题本质上就是空间和时间权衡的艺术。你选择的方案必须依赖题目的数据范围来定这也是为什么我总强调“看数据范围再说解法”。一个 1e5 的数据范围下 p 仍然只有 5出题人摆明了是让你枚举维度千万别把简单问题复杂化。5.3 这题对周赛刷题习惯的三点提醒借着 Round 135 的这道题也顺便说说我对周赛刷题的三点体会。第一拿到题先看数据范围再想算法顺序反了很容易写出一个“理论上正确但实际上超时”的代码。第二对于静态数组的区间查询优先想前缀和、差分、离线而不是条件反射地上线段树、树状数组“工具越重型思考越稀薄”。第三赛后别急着走把每道题的正解思路和别人的优秀代码都看一遍很多所谓的“难题”破绽就在别人的代码注释里写着。我打牛客周赛这么多次最大的感受就是这赛事的题目质量整体在线尤其是中间档位这几道题非常能训练思维的灵活度。Round 135 的区间次方和虽然整体难度不高但踩坑的点特别典型很值得记一轮。下次如果数据里再看到“小范围参数”记得先停下来想想——它可能就是出题人留给你的那扇门。