企业官网建设流程全解析

第一次刷到牛客的每日一题「清楚姐姐买竹鼠」时，我以为是道模拟题：一个可爱的故事背景，买竹鼠、算钱、计数，读完就照着流程写。等我真正把题面捋完才发现，这题藏在故事背后的核心是一类非常经典的区间查询问题——区间次方和。用 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 <= 100；
• n、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^5，q = 10^5，k = 10^9 时，10^5 * 10^5 * 30 = 3 * 10^11 次乘法运算。现代 CPU 一秒钟大概能跑 10^8 到 10^9 次简单运算，这个计算量需要几分钟甚至更久。牛客的评测时限通常只有一两秒，暴力解法必然超时。

有人可能会想：n = 3000，q = 3000 是不是就安全了？3000 * 3000 * 30 = 2.7 * 10^8，Java 跑起来依旧非常吃力，因为取模运算是相对昂贵的操作，加上数组随机访问、循环分支，真实耗时还会放大。这个量级的题目，必须做预处理。

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] = 3，pre[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^18，long 的最大值约 9.22 * 10^18，所以安全。但如果你把 MOD 换成 10^18 级别的数，long * long就会溢出，这种情况必须用更大的类型或分步计算。1e9+7 这个模数选得巧妙，就是为 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 几组必须跑一遍的边界输入

写题不能只盯着样例，样例太温和了。我在本地至少会跑这几组：

对于数组元素 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 跑 n=q=100000、maxK=100 的数据，本地跑了 3 秒多，差点以为二维前缀和方案本身性能不够。换成 BufferedReader 后直接降到 1 秒以内。这提醒我：在线评测里遇到“算法看起来没问题但超时”的情况，先检查输入输出方式。

5.3 不同数据规模下的实测对比

我本地简单测过几种规模，结果可以作为参考：

暴力法在最大规模下完全没法跑，二维前缀和方案的时间主要在预处理那一层。如果 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 刷题，建议把代码里的快读模板和快速幂模板沉淀下来，以后遇到同类问题直接套，会省下大量时间。