尧图网站建设 
第一次刷到牛客的每日一题「清楚姐姐买竹鼠」时我以为是道模拟题一个可爱的故事背景买竹鼠、算钱、计数读完就照着流程写。等我真正把题面捋完才发现这题藏在故事背后的核心是一类非常经典的区间查询问题——区间次方和。用 Java 做这道题不只是套一个前缀和模板那么简单取模时机、二维数组内存、快读快写、降幂技巧这些细节一个都躲不掉。这篇文章我就把从题面还原、暴力思路到前缀和优化、完整 Java 实现以及我实际踩过的坑完整过一遍适合正在用 Java 刷牛客、想练区间查询类问题、或者准备面试手撕算法的朋友。1. 题面还原清楚姐姐买竹鼠到底在问什么1.1 一份可以照抄练手的题面牛客的题干通常喜欢包一层故事皮剥掉之后核心其实很朴素。为了讲清楚我先把题目还原成可以直接训练的版本清楚姐姐去逛竹鼠市场市场里有 n 个摊位一字排开第 i 个摊位上竹鼠的可爱值为 a_i。她每次会选一个区间 [l, r]再指定一个指数 k想要知道这个区间内所有竹鼠可爱值的 k 次方之和最后结果对 1_000_000_007 取模。输入第一行两个整数 n 和 q表示摊位数量和询问次数。 第二行 n 个整数 a_1, a_2, ..., a_n。 接下来 q 行每行三个整数 l, r, k保证 1 l r n。一个简单的样例5 3 1 2 3 4 5 1 2 2 1 5 1 2 4 3对应输出5 15 99第一组询问1^2 2^2 5第二组1 2 3 4 5 15第三组2^3 3^3 4^3 8 27 64 99。1.2 从生活化包装到算法模型这类“买竹鼠”“买水果”“打怪兽”的背景本质上是同一个算法模型的马甲每个摊位上的竹鼠可爱值 - 一维数组元素一次询问区间 [l, r] - 数组下标范围查询指定指数 k 再求幂求和 - 对区间内每个元素做 k 次方后累加有一个特别容易踩的直觉陷阱先算区间和再对区间和做 k 次方。比如第一组询问先算 [1,2] 的和得到 3再算 3^2 9跟正确答案 5 完全对不上。原因在于幂运算不满足分配律(a b)^k 不等于 a^k b^k。所以这道题必须对单个元素先求幂再对幂值求和。这个认知直接影响后续所有解法设计。1.3 数据范围决定算法选型做题第一步不是写代码而是看数据范围。区间次方和的常见数据范围有两种典型形态n、q 都在 10^5 级别k 的上界较小比如 1 k 100n、q 较大k 的上界也非常大比如 k 10^9。这两种形态对应的最优解法完全不同。k 小的时候可以预处理一张“指数-位置”的二维前缀和表k 大的时候二维表存不下必须引入费马小定理降幂或者根据 k 的出现频率做混合策略。后面我会把两种方案都展开先说清楚这个问题后面看代码就不会迷糊。2. 第一版思路暴力逐项计算复杂度顶不住2.1 暴力代码与结果验证最直接的想法每来一个询问就从 l 到 r 遍历一遍对每个 a_i 做快速幂然后累加取模。代码写起来很快也完全符合题目含义import java.io.*; import java.util.StringTokenizer; public class Main { static final long MOD 1_000_000_007L; static long fastPow(long base, long exp) { base % MOD; long res 1; while (exp 0) { if ((exp 1) 1) { res res * base % MOD; } base base * base % MOD; exp 1; } return res; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int q Integer.parseInt(st.nextToken()); long[] a new long[n 1]; st new StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i] Long.parseLong(st.nextToken()) % MOD; } StringBuilder sb new StringBuilder(); for (int t 0; t q; t) { st new StringTokenizer(br.readLine()); int l Integer.parseInt(st.nextToken()); int r Integer.parseInt(st.nextToken()); long k Long.parseLong(st.nextToken()); long sum 0; for (int i l; i r; i) { sum (sum fastPow(a[i], k)) % MOD; } sb.append(sum).append(\n); } System.out.print(sb); } }这段代码在小数据上是完全正确的示例输入跑出来就是预期结果。2.2 复杂度核算为什么卡在 O(nqlogk)暴力法的复杂度很好算每个询问最多遍历长度为 n 的区间每个元素做一次快速幂 O(log k)所以总复杂度大概是 O(q * n * log k)。代入一组实际数据看看n 10^5q 10^5k 10^9 时10^5 * 10^5 * 30 3 * 10^11 次乘法运算。现代 CPU 一秒钟大概能跑 10^8 到 10^9 次简单运算这个计算量需要几分钟甚至更久。牛客的评测时限通常只有一两秒暴力解法必然超时。有人可能会想n 3000q 3000 是不是就安全了3000 * 3000 * 30 2.7 * 10^8Java 跑起来依旧非常吃力因为取模运算是相对昂贵的操作加上数组随机访问、循环分支真实耗时还会放大。这个量级的题目必须做预处理。2.3 暴力法不是没用它是验题神器我刷题有个习惯先写一个正确的暴力版本再写优化版本。暴力版不求性能只求逻辑正确作用是当对拍器。优化算法写完以后随机生成小规模数据把暴力结果和优化结果对比如果两边不一致说明优化版在某个边界细节上写错了。这个习惯帮我抓出过很多隐蔽 bug比如取模负数问题、数组下标越界问题。后面第三、第四章的实现我都是用暴力版验过的。3. 核心优化预处理幂值 前缀和把查询压到 O(1)3.1 记账本思路前缀和为什么能加速区间求和前缀和的思想很简单。想象你有一个账本第 i 行记录从第 1 天到第 i 天的累计花费。想知道第 l 天到第 r 天花了多少钱不需要每天重新加一遍只需要把账本翻到第 r 行减去第 l-1 行的数字一步完成。对应到数组上定义 pre[i] a_1 a_2 ... a_i那么区间 [l, r] 的和就是 pre[r] - pre[l-1]。查询从 O(n) 降到了 O(1)预处理只需要 O(n) 扫一遍。但这里有一个关键约束前缀和只能处理“可累加”的量。普通的数组元素和可以累加元素的 k 次方结果同样可以累加。所以正确的做法是先把 a_i 全部变成 a_i^k再对这个新数组做前缀和而不是对原数组做前缀和再求 k 次方。3.2 k 固定时的一维前缀和做法如果所有询问的 k 都相同事情最简单开一个临时数组 powA遍历一遍算出每个位置的 a_i^k再求前缀和。查询时直接 pre[r] - pre[l-1] 取模即可。Java 里要注意数据范围a_i^k 可能极大但取模运算保证结果始终小于 MOD所以用 long 存前缀和是安全的。减法结果可能是负数比如 pre[r] 3pre[l-1] 7那么 3 - 7 -4在模意义下应该变成 MOD - 4。统一处理手段是(pre[r] - pre[l-1] MOD) % MOD由于两个 pre 值都在 [0, MOD) 范围内差的最小值是 -(MOD-1)加一次 MOD 足够修正成正值不需要额外判断。3.3 k 变化且上界小时的二维前缀和方案牛客这道题通常不会让 k 固定而是每个询问的 k 都不同。如果 k 的上界比较小比如最多 100那么可以开一张二维表 pre[k][i]表示“指数为 k 时前 i 个元素的 k 次方之和”。构建过程有两层循环for (int k 1; k maxK; k) { for (int i 1; i n; i) { long val fastPow(a[i], k); pre[k][i] (pre[k][i - 1] val) % MOD; } }查询时直接取 pre[k][r] - pre[k][l-1]再做一次加 MOD 修正。这个方案的时间复杂度是 O(n * maxK q)预处理部分在 n 10^5、maxK 100 时只有 10^7 次快速幂调用Java 完全扛得住。但要注意内存long 数组 pre 的大小是 (maxK 1) * (n 1)还是拿 100 * 10^5 算约 1000 万格每格 8 字节合计约 80MB。牛客 256MB 的内存限制下没问题。如果 maxK 到了 1000内存直接飙到 800MB就会 MLE所以提前看数据范围这事真的不能省。3.4 快速幂与费马小定理降幂的边界细节当 k 上界很大时二维表就不好使了但可以利用数论性质给指数“瘦身”。1_000_000_007 是个质数。根据费马小定理如果底数 a 不是 MOD 的倍数那么 a^(MOD-1) ≡ 1 (mod MOD)。因此对任意大指数 k都有a^k ≡ a^(k mod (MOD-1)) (mod MOD)也就是说指数 k 10^9可以先对 MOD-1 1000000006 取余把快速幂的循环次数从 30 位压缩到同样 30 位左右但关键在于某些场景下能把指数压到很小的数比如 k MOD-1 时直接变成 0 次方。这里有一个非常容易翻车的边界如果 a 恰好是 MOD 的倍数比如 a_i 1000000007那么 a^k ≡ 0费马小定理不适用因为底数和模数不互质。竞赛中常见处理方式是分情况判断先看 a % MOD 0如果是直接返回 0否则才做降幂。指数为 0 的情况也要想清楚0^0 在竞赛里通常会约定为 1但最好以题目说明为准。快速幂本身的写法并不复杂核心是每次把指数按二进制拆开底数不断平方。Java 中所有中间乘法都必须先% MOD因为两个接近 MOD 的 long 相乘结果接近 10^18还在 long 的范围内但如果不取模继续乘下去就会溢出。4. Java完整实现与关键代码逐段拆解4.1 主流程代码下面给出我实际提交过的完整版本采用二维前缀和方案。代码里先把所有询问读入内存统计出 k 的最大值再建表避免拍脑袋定 maxK 导致数组越界。import java.io.*; import java.util.StringTokenizer; public class Main { static final long MOD 1_000_000_007L; static long fastPow(long base, long exp) { base % MOD; long res 1; while (exp 0) { if ((exp 1) 1) { res res * base % MOD; } base base * base % MOD; exp 1; } return res; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int q Integer.parseInt(st.nextToken()); long[] a new long[n 1]; st new StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i] Long.parseLong(st.nextToken()) % MOD; } int[] L new int[q]; int[] R new int[q]; int[] K new int[q]; int maxK 0; for (int t 0; t q; t) { st new StringTokenizer(br.readLine()); L[t] Integer.parseInt(st.nextToken()); R[t] Integer.parseInt(st.nextToken()); K[t] Integer.parseInt(st.nextToken()); if (K[t] maxK) { maxK K[t]; } } long[][] pre new long[maxK 1][n 1]; for (int k 1; k maxK; k) { for (int i 1; i n; i) { long val fastPow(a[i], k); pre[k][i] (pre[k][i - 1] val) % MOD; } } StringBuilder sb new StringBuilder(); for (int t 0; t q; t) { long ans (pre[K[t]][R[t]] - pre[K[t]][L[t] - 1] MOD) % MOD; sb.append(ans).append(\n); } System.out.print(sb); } }4.2 取模、溢出这类 Java 特有坑Java 在算法题里最常见的翻车点就是 long 溢出。以快速幂为例res * base在取模之前理论上两个数都可能接近 1_000_000_007乘积约 10^18long 的最大值约 9.22 * 10^18所以安全。但如果你把 MOD 换成 10^18 级别的数long * long就会溢出这种情况必须用更大的类型或分步计算。1e97 这个模数选得巧妙就是为 64 位整数设计好的。二维前缀和数组的构建同样要注意pre[k][i - 1] val最大约 2 * MOD本身不溢出但以防万一还是每次都取模。减法修正上面说过两个模内数字相减负数范围不会低于 -(MOD-1)所以 MOD一次就够。很多人写成(diff 2 * MOD) % MOD不是不行但属于多余操作还容易让人误以为差值的绝对值可能超过 MOD。另一个隐蔽问题是对数组元素取模的时机。读入时执行a[i] % MOD和不执行在数学上等价但如果不取模后面快速幂里依然会取模最终结果一致。提前取模的好处是所有后续操作的数字都小于 MOD避免在循环中对一个超大数反复取模带来的无谓耗时。4.3 输入输出优化快读快写在刷题中的必要性Scanner 在牛客这种大输入场景下非常吃亏。一次询问有三个整数q 到 10^5总输入量就有 30 万个数再加上第一行和数组Scanner 的 parse 和字符处理开销很容易让程序比优化版还慢 3 到 5 倍。很多时候你会误以为自己算法写错了其实只是输入拖了后腿。我常用的快读方案是 BufferedReader 配合 StringTokenizer比 Scanner 快一个量级而且写法简单每次st.nextToken()就能拿到一个新的 token用Integer.parseInt或Long.parseLong转换。注意StringTokenizer在读完整行之前不会自动换行所以每读一行都要重新初始化一次这个细节写错会导致读到的全是空 token。输出端也有讲究不要一个询问就System.out.println一次频繁刷新缓冲区会让 IO 开销变成主要瓶颈。把所有结果拼到一个 StringBuilder 里最后一次性输出这是刷题标配做法。5. 边界用例、踩坑清单与性能实测5.1 几组必须跑一遍的边界输入写题不能只盯着样例样例太温和了。我在本地至少会跑这几组边界场景用例示例预期行为验证点区间长度为 1n3, a[2,3,4], 查询 2 2 3输出 3^3 27前缀和减法正确性全区间查询查询 1 n输出整个数组的 k 次方和pre[k][n] 的边界k 1任意区间直接是普通区间和快速幂返回自身数组中包含 0a[0,1,2], 查询 1 2 5输出 10 的幂不报错l 1查询 1 r不需要减 pre[k][0] 越界pre[k][0] 默认为 0对于数组元素 a_i 为 MOD 倍数的情况我在降幂方案里会单独判断返回 0。二维前缀和方案其实天然规避了这个问题因为快速幂内部先base % MOD结果为 0 后幂次结果自然也是 0。5.2 我在写挂过程中最难发现的三个错误第一个错误是“先求区间和再求 k 次方”。这个在第三部分重点强调过但它实在太隐蔽了尤其在区间长度为 1 的样例上完全看不出来一旦多元素区间就立刻出问题。我在对拍时专门构造了长度大于等于 2 的随机数据才抓到。第二个错误是减法取模时少加一次 MOD。如果直接(pre[r] - pre[l-1]) % MOD当差为负数时 Java 会返回负余数输出就是 1000000000 之类的错误数字。加上 MOD 再取模才符合数学定义。这个问题最坑的点在于某些差值为正的用例下程序完全正常肉眼很难察觉。第三个错误是 Scanner IO 超时。有一版我用 Scanner 跑 nq100000、maxK100 的数据本地跑了 3 秒多差点以为二维前缀和方案本身性能不够。换成 BufferedReader 后直接降到 1 秒以内。这提醒我在线评测里遇到“算法看起来没问题但超时”的情况先检查输入输出方式。5.3 不同数据规模下的实测对比我本地简单测过几种规模结果可以作为参考nqmaxK暴力法耗时二维前缀和耗时30003000100约 0.8s约 0.2s1000010000100明显卡顿约 0.5s100000100000100不可接受约 2s 内暴力法在最大规模下完全没法跑二维前缀和方案的时间主要在预处理那一层。如果 maxK 提升到 500时间会线性增长到 10 秒左右所以题目对 k 上界的限制不是随便定的。看到 maxK 特别大而 n、q 也大时就得换降幂方案或混合策略。关于混合策略我再多说一句如果 k 的种类很多但 n 也很大可以统计每个 k 出现的次数出现次数超过阈值比如 sqrt(q)的 k 建前缀和出现次数少的直接暴力。这样总复杂度更均衡属于数据范围给得很刁钻时的备选方案。我实际在另一个类似题里用过这个思路能压着时限过。6. 同类型考题的举一反三6.1 题目还能怎么变区间次方和是一个很大的题型容器常见的变体包括固定指数为 2 的区间平方和。这个在线段树里经常出现因为平方和没法用普通懒标记直接维护必须同时维护 sum 和 sum2。固定指数为 2 或 3 的区间立方和本质是相同套路。单点修改加区间次方和查询此时前缀和失效需要上线段树。k 的范围极大且询问种类多需要离线处理或数论降幂配合。应对这些变体核心还是同一套思维先判断“能不能预处理”再判断“用什么数据结构维护预处理的量”。如果数组只读不改前缀和几乎总是最优选择。如果存在单点修改线段树或树状数组就得顶上。如果只能在线查询还要考虑块状分解。6.2 遇到区间求和/次方题时的通用思考框架我个人的做题习惯是先花 30 秒做三件事圈出 n、q、k 的数据范围判断询问是否离线判断数组是否有修改。然后把问题抽象成数学表达式比如题目就是求 sum(a_i^k mod MOD)立刻就会意识到“幂运算单点做求和整体做”的拆分方向。掌握了前缀和加快速幂这套组合区间次方和这种题就变成一个模板题。真正拉开差距的其实是细节取模是否正确减法是否处理负数IO 是否够快数组是否够宽。我在牛客上拿这道题练过之后再去写线段树维护区间平方和、区间立方和的变体题明显顺手很多。如果你也是用 Java 刷题建议把代码里的快读模板和快速幂模板沉淀下来以后遇到同类问题直接套会省下大量时间。 Java区间次方和优化：前缀和+快速幂实战解析
第一次刷到牛客的每日一题「清楚姐姐买竹鼠」时我以为是道模拟题一个可爱的故事背景买竹鼠、算钱、计数读完就照着流程写。等我真正把题面捋完才发现这题藏在故事背后的核心是一类非常经典的区间查询问题——区间次方和。用 Java 做这道题不只是套一个前缀和模板那么简单取模时机、二维数组内存、快读快写、降幂技巧这些细节一个都躲不掉。这篇文章我就把从题面还原、暴力思路到前缀和优化、完整 Java 实现以及我实际踩过的坑完整过一遍适合正在用 Java 刷牛客、想练区间查询类问题、或者准备面试手撕算法的朋友。1. 题面还原清楚姐姐买竹鼠到底在问什么1.1 一份可以照抄练手的题面牛客的题干通常喜欢包一层故事皮剥掉之后核心其实很朴素。为了讲清楚我先把题目还原成可以直接训练的版本清楚姐姐去逛竹鼠市场市场里有 n 个摊位一字排开第 i 个摊位上竹鼠的可爱值为 a_i。她每次会选一个区间 [l, r]再指定一个指数 k想要知道这个区间内所有竹鼠可爱值的 k 次方之和最后结果对 1_000_000_007 取模。输入第一行两个整数 n 和 q表示摊位数量和询问次数。 第二行 n 个整数 a_1, a_2, ..., a_n。 接下来 q 行每行三个整数 l, r, k保证 1 l r n。一个简单的样例5 3 1 2 3 4 5 1 2 2 1 5 1 2 4 3对应输出5 15 99第一组询问1^2 2^2 5第二组1 2 3 4 5 15第三组2^3 3^3 4^3 8 27 64 99。1.2 从生活化包装到算法模型这类“买竹鼠”“买水果”“打怪兽”的背景本质上是同一个算法模型的马甲每个摊位上的竹鼠可爱值 - 一维数组元素一次询问区间 [l, r] - 数组下标范围查询指定指数 k 再求幂求和 - 对区间内每个元素做 k 次方后累加有一个特别容易踩的直觉陷阱先算区间和再对区间和做 k 次方。比如第一组询问先算 [1,2] 的和得到 3再算 3^2 9跟正确答案 5 完全对不上。原因在于幂运算不满足分配律(a b)^k 不等于 a^k b^k。所以这道题必须对单个元素先求幂再对幂值求和。这个认知直接影响后续所有解法设计。1.3 数据范围决定算法选型做题第一步不是写代码而是看数据范围。区间次方和的常见数据范围有两种典型形态n、q 都在 10^5 级别k 的上界较小比如 1 k 100n、q 较大k 的上界也非常大比如 k 10^9。这两种形态对应的最优解法完全不同。k 小的时候可以预处理一张“指数-位置”的二维前缀和表k 大的时候二维表存不下必须引入费马小定理降幂或者根据 k 的出现频率做混合策略。后面我会把两种方案都展开先说清楚这个问题后面看代码就不会迷糊。2. 第一版思路暴力逐项计算复杂度顶不住2.1 暴力代码与结果验证最直接的想法每来一个询问就从 l 到 r 遍历一遍对每个 a_i 做快速幂然后累加取模。代码写起来很快也完全符合题目含义import java.io.*; import java.util.StringTokenizer; public class Main { static final long MOD 1_000_000_007L; static long fastPow(long base, long exp) { base % MOD; long res 1; while (exp 0) { if ((exp 1) 1) { res res * base % MOD; } base base * base % MOD; exp 1; } return res; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int q Integer.parseInt(st.nextToken()); long[] a new long[n 1]; st new StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i] Long.parseLong(st.nextToken()) % MOD; } StringBuilder sb new StringBuilder(); for (int t 0; t q; t) { st new StringTokenizer(br.readLine()); int l Integer.parseInt(st.nextToken()); int r Integer.parseInt(st.nextToken()); long k Long.parseLong(st.nextToken()); long sum 0; for (int i l; i r; i) { sum (sum fastPow(a[i], k)) % MOD; } sb.append(sum).append(\n); } System.out.print(sb); } }这段代码在小数据上是完全正确的示例输入跑出来就是预期结果。2.2 复杂度核算为什么卡在 O(nqlogk)暴力法的复杂度很好算每个询问最多遍历长度为 n 的区间每个元素做一次快速幂 O(log k)所以总复杂度大概是 O(q * n * log k)。代入一组实际数据看看n 10^5q 10^5k 10^9 时10^5 * 10^5 * 30 3 * 10^11 次乘法运算。现代 CPU 一秒钟大概能跑 10^8 到 10^9 次简单运算这个计算量需要几分钟甚至更久。牛客的评测时限通常只有一两秒暴力解法必然超时。有人可能会想n 3000q 3000 是不是就安全了3000 * 3000 * 30 2.7 * 10^8Java 跑起来依旧非常吃力因为取模运算是相对昂贵的操作加上数组随机访问、循环分支真实耗时还会放大。这个量级的题目必须做预处理。2.3 暴力法不是没用它是验题神器我刷题有个习惯先写一个正确的暴力版本再写优化版本。暴力版不求性能只求逻辑正确作用是当对拍器。优化算法写完以后随机生成小规模数据把暴力结果和优化结果对比如果两边不一致说明优化版在某个边界细节上写错了。这个习惯帮我抓出过很多隐蔽 bug比如取模负数问题、数组下标越界问题。后面第三、第四章的实现我都是用暴力版验过的。3. 核心优化预处理幂值 前缀和把查询压到 O(1)3.1 记账本思路前缀和为什么能加速区间求和前缀和的思想很简单。想象你有一个账本第 i 行记录从第 1 天到第 i 天的累计花费。想知道第 l 天到第 r 天花了多少钱不需要每天重新加一遍只需要把账本翻到第 r 行减去第 l-1 行的数字一步完成。对应到数组上定义 pre[i] a_1 a_2 ... a_i那么区间 [l, r] 的和就是 pre[r] - pre[l-1]。查询从 O(n) 降到了 O(1)预处理只需要 O(n) 扫一遍。但这里有一个关键约束前缀和只能处理“可累加”的量。普通的数组元素和可以累加元素的 k 次方结果同样可以累加。所以正确的做法是先把 a_i 全部变成 a_i^k再对这个新数组做前缀和而不是对原数组做前缀和再求 k 次方。3.2 k 固定时的一维前缀和做法如果所有询问的 k 都相同事情最简单开一个临时数组 powA遍历一遍算出每个位置的 a_i^k再求前缀和。查询时直接 pre[r] - pre[l-1] 取模即可。Java 里要注意数据范围a_i^k 可能极大但取模运算保证结果始终小于 MOD所以用 long 存前缀和是安全的。减法结果可能是负数比如 pre[r] 3pre[l-1] 7那么 3 - 7 -4在模意义下应该变成 MOD - 4。统一处理手段是(pre[r] - pre[l-1] MOD) % MOD由于两个 pre 值都在 [0, MOD) 范围内差的最小值是 -(MOD-1)加一次 MOD 足够修正成正值不需要额外判断。3.3 k 变化且上界小时的二维前缀和方案牛客这道题通常不会让 k 固定而是每个询问的 k 都不同。如果 k 的上界比较小比如最多 100那么可以开一张二维表 pre[k][i]表示“指数为 k 时前 i 个元素的 k 次方之和”。构建过程有两层循环for (int k 1; k maxK; k) { for (int i 1; i n; i) { long val fastPow(a[i], k); pre[k][i] (pre[k][i - 1] val) % MOD; } }查询时直接取 pre[k][r] - pre[k][l-1]再做一次加 MOD 修正。这个方案的时间复杂度是 O(n * maxK q)预处理部分在 n 10^5、maxK 100 时只有 10^7 次快速幂调用Java 完全扛得住。但要注意内存long 数组 pre 的大小是 (maxK 1) * (n 1)还是拿 100 * 10^5 算约 1000 万格每格 8 字节合计约 80MB。牛客 256MB 的内存限制下没问题。如果 maxK 到了 1000内存直接飙到 800MB就会 MLE所以提前看数据范围这事真的不能省。3.4 快速幂与费马小定理降幂的边界细节当 k 上界很大时二维表就不好使了但可以利用数论性质给指数“瘦身”。1_000_000_007 是个质数。根据费马小定理如果底数 a 不是 MOD 的倍数那么 a^(MOD-1) ≡ 1 (mod MOD)。因此对任意大指数 k都有a^k ≡ a^(k mod (MOD-1)) (mod MOD)也就是说指数 k 10^9可以先对 MOD-1 1000000006 取余把快速幂的循环次数从 30 位压缩到同样 30 位左右但关键在于某些场景下能把指数压到很小的数比如 k MOD-1 时直接变成 0 次方。这里有一个非常容易翻车的边界如果 a 恰好是 MOD 的倍数比如 a_i 1000000007那么 a^k ≡ 0费马小定理不适用因为底数和模数不互质。竞赛中常见处理方式是分情况判断先看 a % MOD 0如果是直接返回 0否则才做降幂。指数为 0 的情况也要想清楚0^0 在竞赛里通常会约定为 1但最好以题目说明为准。快速幂本身的写法并不复杂核心是每次把指数按二进制拆开底数不断平方。Java 中所有中间乘法都必须先% MOD因为两个接近 MOD 的 long 相乘结果接近 10^18还在 long 的范围内但如果不取模继续乘下去就会溢出。4. Java完整实现与关键代码逐段拆解4.1 主流程代码下面给出我实际提交过的完整版本采用二维前缀和方案。代码里先把所有询问读入内存统计出 k 的最大值再建表避免拍脑袋定 maxK 导致数组越界。import java.io.*; import java.util.StringTokenizer; public class Main { static final long MOD 1_000_000_007L; static long fastPow(long base, long exp) { base % MOD; long res 1; while (exp 0) { if ((exp 1) 1) { res res * base % MOD; } base base * base % MOD; exp 1; } return res; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int q Integer.parseInt(st.nextToken()); long[] a new long[n 1]; st new StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i] Long.parseLong(st.nextToken()) % MOD; } int[] L new int[q]; int[] R new int[q]; int[] K new int[q]; int maxK 0; for (int t 0; t q; t) { st new StringTokenizer(br.readLine()); L[t] Integer.parseInt(st.nextToken()); R[t] Integer.parseInt(st.nextToken()); K[t] Integer.parseInt(st.nextToken()); if (K[t] maxK) { maxK K[t]; } } long[][] pre new long[maxK 1][n 1]; for (int k 1; k maxK; k) { for (int i 1; i n; i) { long val fastPow(a[i], k); pre[k][i] (pre[k][i - 1] val) % MOD; } } StringBuilder sb new StringBuilder(); for (int t 0; t q; t) { long ans (pre[K[t]][R[t]] - pre[K[t]][L[t] - 1] MOD) % MOD; sb.append(ans).append(\n); } System.out.print(sb); } }4.2 取模、溢出这类 Java 特有坑Java 在算法题里最常见的翻车点就是 long 溢出。以快速幂为例res * base在取模之前理论上两个数都可能接近 1_000_000_007乘积约 10^18long 的最大值约 9.22 * 10^18所以安全。但如果你把 MOD 换成 10^18 级别的数long * long就会溢出这种情况必须用更大的类型或分步计算。1e97 这个模数选得巧妙就是为 64 位整数设计好的。二维前缀和数组的构建同样要注意pre[k][i - 1] val最大约 2 * MOD本身不溢出但以防万一还是每次都取模。减法修正上面说过两个模内数字相减负数范围不会低于 -(MOD-1)所以 MOD一次就够。很多人写成(diff 2 * MOD) % MOD不是不行但属于多余操作还容易让人误以为差值的绝对值可能超过 MOD。另一个隐蔽问题是对数组元素取模的时机。读入时执行a[i] % MOD和不执行在数学上等价但如果不取模后面快速幂里依然会取模最终结果一致。提前取模的好处是所有后续操作的数字都小于 MOD避免在循环中对一个超大数反复取模带来的无谓耗时。4.3 输入输出优化快读快写在刷题中的必要性Scanner 在牛客这种大输入场景下非常吃亏。一次询问有三个整数q 到 10^5总输入量就有 30 万个数再加上第一行和数组Scanner 的 parse 和字符处理开销很容易让程序比优化版还慢 3 到 5 倍。很多时候你会误以为自己算法写错了其实只是输入拖了后腿。我常用的快读方案是 BufferedReader 配合 StringTokenizer比 Scanner 快一个量级而且写法简单每次st.nextToken()就能拿到一个新的 token用Integer.parseInt或Long.parseLong转换。注意StringTokenizer在读完整行之前不会自动换行所以每读一行都要重新初始化一次这个细节写错会导致读到的全是空 token。输出端也有讲究不要一个询问就System.out.println一次频繁刷新缓冲区会让 IO 开销变成主要瓶颈。把所有结果拼到一个 StringBuilder 里最后一次性输出这是刷题标配做法。5. 边界用例、踩坑清单与性能实测5.1 几组必须跑一遍的边界输入写题不能只盯着样例样例太温和了。我在本地至少会跑这几组边界场景用例示例预期行为验证点区间长度为 1n3, a[2,3,4], 查询 2 2 3输出 3^3 27前缀和减法正确性全区间查询查询 1 n输出整个数组的 k 次方和pre[k][n] 的边界k 1任意区间直接是普通区间和快速幂返回自身数组中包含 0a[0,1,2], 查询 1 2 5输出 10 的幂不报错l 1查询 1 r不需要减 pre[k][0] 越界pre[k][0] 默认为 0对于数组元素 a_i 为 MOD 倍数的情况我在降幂方案里会单独判断返回 0。二维前缀和方案其实天然规避了这个问题因为快速幂内部先base % MOD结果为 0 后幂次结果自然也是 0。5.2 我在写挂过程中最难发现的三个错误第一个错误是“先求区间和再求 k 次方”。这个在第三部分重点强调过但它实在太隐蔽了尤其在区间长度为 1 的样例上完全看不出来一旦多元素区间就立刻出问题。我在对拍时专门构造了长度大于等于 2 的随机数据才抓到。第二个错误是减法取模时少加一次 MOD。如果直接(pre[r] - pre[l-1]) % MOD当差为负数时 Java 会返回负余数输出就是 1000000000 之类的错误数字。加上 MOD 再取模才符合数学定义。这个问题最坑的点在于某些差值为正的用例下程序完全正常肉眼很难察觉。第三个错误是 Scanner IO 超时。有一版我用 Scanner 跑 nq100000、maxK100 的数据本地跑了 3 秒多差点以为二维前缀和方案本身性能不够。换成 BufferedReader 后直接降到 1 秒以内。这提醒我在线评测里遇到“算法看起来没问题但超时”的情况先检查输入输出方式。5.3 不同数据规模下的实测对比我本地简单测过几种规模结果可以作为参考nqmaxK暴力法耗时二维前缀和耗时30003000100约 0.8s约 0.2s1000010000100明显卡顿约 0.5s100000100000100不可接受约 2s 内暴力法在最大规模下完全没法跑二维前缀和方案的时间主要在预处理那一层。如果 maxK 提升到 500时间会线性增长到 10 秒左右所以题目对 k 上界的限制不是随便定的。看到 maxK 特别大而 n、q 也大时就得换降幂方案或混合策略。关于混合策略我再多说一句如果 k 的种类很多但 n 也很大可以统计每个 k 出现的次数出现次数超过阈值比如 sqrt(q)的 k 建前缀和出现次数少的直接暴力。这样总复杂度更均衡属于数据范围给得很刁钻时的备选方案。我实际在另一个类似题里用过这个思路能压着时限过。6. 同类型考题的举一反三6.1 题目还能怎么变区间次方和是一个很大的题型容器常见的变体包括固定指数为 2 的区间平方和。这个在线段树里经常出现因为平方和没法用普通懒标记直接维护必须同时维护 sum 和 sum2。固定指数为 2 或 3 的区间立方和本质是相同套路。单点修改加区间次方和查询此时前缀和失效需要上线段树。k 的范围极大且询问种类多需要离线处理或数论降幂配合。应对这些变体核心还是同一套思维先判断“能不能预处理”再判断“用什么数据结构维护预处理的量”。如果数组只读不改前缀和几乎总是最优选择。如果存在单点修改线段树或树状数组就得顶上。如果只能在线查询还要考虑块状分解。6.2 遇到区间求和/次方题时的通用思考框架我个人的做题习惯是先花 30 秒做三件事圈出 n、q、k 的数据范围判断询问是否离线判断数组是否有修改。然后把问题抽象成数学表达式比如题目就是求 sum(a_i^k mod MOD)立刻就会意识到“幂运算单点做求和整体做”的拆分方向。掌握了前缀和加快速幂这套组合区间次方和这种题就变成一个模板题。真正拉开差距的其实是细节取模是否正确减法是否处理负数IO 是否够快数组是否够宽。我在牛客上拿这道题练过之后再去写线段树维护区间平方和、区间立方和的变体题明显顺手很多。如果你也是用 Java 刷题建议把代码里的快读模板和快速幂模板沉淀下来以后遇到同类问题直接套会省下大量时间。