先声明一下，今天聊的MOD是模运算的mod，不是游戏模组那种MOD。这篇文章要解决的是算法题里非常高频的一类问题：给定数组，统计满足某种整除或取模条件的子数组。这类题拿到手如果直接双重循环去枚举左右端点，数据量一到10万级别就必挂。我见过太多人在这个坑里栽跟头，所以把同余转化和桶优化这套组合套路彻底拆开讲一遍，从数学推导到代码实现，从经典题目到变种扩展，一次说透。
1. 同余转化：把“整除判断”翻译成“余数相等”
1.1 先从一个高频问题说起
力扣第974题“和可被 K 整除的子数组”，是我刷题这么多年遇到的最典型的同余应用。很多人第一次看到这个题目，第一反应都是：枚举左端点、枚举右端点、算区间和、判断能不能整除K。思路不能说错，但复杂度完全失控。n是10^5时，n(n+1)/2个区间，算一遍就是10^10级别操作，稳稳超时。
换个角度想，判断“某个整数能不能被K整除”，本质上就是判断“这个整数模K是不是余0”。那如果我们能把区间和这种动态变化的东西，转换成一个容易维护的静态属性，问题就好办了。前缀和就是干这个的。一旦引入前缀和，整个问题就从“算一堆区间和”变成了“比较两个前缀和的关系”，这一步是今天所有内容的起点。
1.2 前缀和公式推导：区间和怎么变成余数比较
先写下基础定义。pre[i]表示数组前i个元素的和，并且规定pre[0] = 0，表示一个元素都不取的“空前缀”。那么从下标l到下标r这个区间的和，就等于pre[r + 1] - pre[l]。这是前缀和的标准用法，背熟就行。
现在关键来了。我们要求的是区间和能被K整除，也就是：
(pre[r + 1] - pre[l]) % K == 0
这个式子等价于什么？等价于pre[r + 1]和pre[l]在模K意义下余数相同，写成：
pre[r + 1] % K == pre[l] % K
这步转化就是整个算法里最核心的“同余转化”。你可以用带余除法验证一下：两个数之差能被K整除，当且仅当这两个数除以K的余数相等。比如11和1，都除以5，余数分别是1和1，所以11 - 1 = 10能被5整除。再比如7和2，余数分别是2和2，所以7 - 2 = 5也能被5整除。
一旦抓住这个等价关系，“统计能被K整除的子数组数量”就变成了“统计有多少对前缀和的余数相等”。问题性质完全不同了。
1.3 为什么转化后复杂度能降一个量级
暴力做法要枚举所有l和r，组合数是n(n+1)/2，复杂度O(n^2)。同余转化之后，我们只需要从左到右扫一遍数组，每扫到一个位置，问一个问题：当前这个前缀和的余数，之前出现过几次？每出现一次，就说明能和之前某个前缀配成一对，产生一个合法子数组。
为什么配对数量可以直接累加？因为余数相同的关系是等价关系：如果pre[a]余数是r，pre[b]余数也是r，那么pre[a]和pre[b]的差一定被K整除，对应的区间一定合法。反过来，如果区间合法，两个端点的前缀和余数一定相同。所以一对一同余的前缀和，就是一个合法子数组，不多不少。
这个思路的本质是把问题从“笛卡尔积式的两两比较”压缩成了“线性扫描加查表”。我打个比方：班里统计生日相差能被7整除的同学对数，暴力做法是两两比较365天；聪明做法是按星期几分成7组，只需要统计组内组合数。这个“按星期几分组”的动作，就是桶优化的雏形，下一章细说。
2. 桶优化：用计数器把两层循环压成一层
2.1 桶里到底存什么
同余转化做完以后，我们需要一个数据结构，把“余数”映射到“出现次数”。这个数据结构就是桶。桶的下标是余数，桶里存的值是这个余数已经出现了几次。
遍历到每个元素时，把当前前缀和pre取模得到r，然后做两件事：第一，ans加上cnt[r]；第二，把cnt[r]自增1。顺序绝对不能反。如果先自增再累加，就会把当前前缀和自己跟自己配对的情况也算进去，形成一个长度为零的“空子数组”，导致答案多算。
为了加深理解，看一个最简单的例子。nums = [5], K = 5。初始化桶cnt = {0: 1}。扫到5，pre = 5，r = 0，ans += cnt[0]也就是1，然后cnt[0]变成2。最终答案是1。这里ans加上的1，对应的就是子数组[5]本身。如果没有提前把余数0放进桶里，答案就会算成0，全错。这个初始化细节我在第5章还要重点强调，它是新手最容易漏的地方。
2.2 负余数陷阱：统一模系
取模运算有个让人头疼的细节：负数怎么取余。C++和Java里，-2 % 5的结果是-2，而Python里-2 % 5的结果是3。如果拿到一个负余数直接去访问数组下标或者作为哈希键，程序会直接出问题，要么越界，要么统计出错。
统一处理方式是用一个防御性公式：
r = (pre % K + K) % K
这个式子的原理很简单：pre % K先把结果限制在(-K, K)区间内，加上K以后变成(0, 2K)区间内的正数，再取一次模，结果必然落在[0, K-1]。无论pre是正是负，最终得到的r都是合法的非负余数。
我用一个具体例子演示为什么要这样处理。假设K = 5，某个前缀和pre = -2。在C++里直接-2 % 5得到-2，把这个-2作为桶下标，访问cnt[-2]显然不对。用公式算一下：(-2 % 5 + 5) % 5 = (-2 + 5) % 5 = 3 % 5 = 3，正确余数是3。因为-2和3在模5意义下确实同余，-2 = 5 * (-1) + 3。
2.3 数组桶 vs 哈希桶，怎么选
实现桶有两种常见方式，选择标准主要看K的大小。
第一种，K在10^6甚至10^5以内时，直接开一个长度为K的整型数组。初始化全0。数组下标访问是O(1)，常数极小，而且是连续内存，缓存命中率高，实测性能远好于一切哈希结构。
第二种，K非常大，比如1e9，根本开不了那么大的数组，就只能用哈希表，只存储出现过的余数。时间上仍然是O(n)，但因为哈希碰撞、扩容等原因，常数比数组大不少。
我个人的选型原则是：竞赛或者面试环境里能开数组就开数组，空间换时间非常划算。只有K确实大到没法开数组时才用哈希。原因很简单，数组桶最坏情况就是k个位置的随机访问，性能可预期；哈希桶在最坏情况下可能因为碰撞严重而退化成O(n^2)，虽然实际很少出现，但没必要给自己留隐患。
| 方案 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力双重循环 | O(n^2) | O(1) | n ≤ 1000 |
| 前缀和 + 数组桶 | O(n) | O(K) | K ≤ 10^6，性能最优 |
| 前缀和 + 哈希桶 | O(n) | O(n)，只存出现过的余数 | K任意，K很大时使用 |
3. 从零实操：三道经典题的思路、代码与手推
3.1 题一：和可被K整除的子数组（力扣974）
题目描述很长，核心就一句：给一个整数数组nums和一个整数K，返回数组中能被子数组和整除K的连续非空子数组的数目。
标准解法就是前缀和加同余桶。Python代码非常干净：
def subarraysDivByK(nums, k): cnt = {0: 1} pre = 0 ans = 0 for x in nums: pre += x r = pre % k # Python的%保证结果为非负 ans += cnt.get(r, 0) cnt[r] = cnt.get(r, 0) + 1 return ansC++版本需要注意负数取模的问题：
int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int, int> cnt; cnt[0] = 1; int pre = 0, ans = 0; for (int x : nums) { pre += x; int r = (pre % k + k) % k; // 统一非负余数 ans += cnt[r]; cnt[r]++; } return ans; }我用题目自带的示例nums = [4,5,0,-2,-3,1], K = 5，一步一步手推一遍。这个过程非常重要，建议你自己也在纸上跟着画一遍。
定义桶cnt，初始状态是cnt[0] = 1，表示空前缀pre[0] = 0的余数0已经出现一次。然后逐个扫描：
| 扫描元素 | 当前pre | 余数r | 累加前cnt[r] | ans更新 | 更新后cnt |
|---|---|---|---|---|---|
| 初始 | - | - | - | 0 | {0:1} |
| 4 | 4 | 4 | 0 | 0 | {0:1, 4:1} |
| 5 | 9 | 4 | 1 | 1 | {0:1, 4:2} |
| 0 | 9 | 4 | 2 | 3 | {0:1, 4:3} |
| -2 | 7 | 2 | 0 | 3 | {0:1, 4:3, 2:1} |
| -3 | 4 | 4 | 3 | 6 | {0:1, 4:4, 2:1} |
| 1 | 5 | 0 | 1 | 7 | {0:2, 4:4, 2:1} |
最终答案是7，和官方示例输出一致。这张表建议多看两遍，你就能直观理解“每遇到一个已经出现过的余数，就多了一批新的合法配对”这个逻辑。比如扫到第三个元素0时，余数4已经出现过两次，所以ans从1变成3，说明新增了两个合法子数组。
3.2 题二：和为K的子数组（力扣560）——同余桶的“近亲”
力扣560题是“和为K的子数组”，虽然名字里没有“整除”，但它和974题共用同一个前缀和加桶的框架。唯一区别是，974题比的是“余数相等”，560题比的是“差值等于K”。
推导过程是这样的：要sum(l..r) == K，等价于pre[r + 1] - pre[l] == K，也就是pre[l] == pre[r + 1] - K。所以每扫到一个位置，答案要加上“之前有多少个前缀和恰好等于当前pre - K”，然后把当前pre放入桶中。
def subarraySum(nums, k): cnt = {0: 1} pre = 0 ans = 0 for x in nums: pre += x ans += cnt.get(pre - k, 0) cnt[pre] = cnt.get(pre, 0) + 1 return ans注意这里桶的键不是余数，而是真实的前缀和值。你能清楚区分974题和560题的差别，说明你真正理解了前缀和加桶的通用框架。两题的代码结构几乎一模一样，唯一的灵魂差异就是“桶里存什么、查什么”。
3.3 题三：最长的和能被K整除的子数组
再升级一下：不统计数量，要长度。思路同样用同余桶，但桶里不再存“出现次数”，而是存“某个余数第一次出现的位置”。
维护一个字典first，key是前缀和的余数，value是这个余数第一次出现的下标位置。注意这里的下标我用“已扫描元素个数”表示。扫描过程中，如果当前余数已经出现过，就用当前位置减去first[r]，得到一个候选长度，更新最大值；如果没出现过，就记录first[r]为当前位置。
def max_len_divisible(nums, k): first = {0: 0} pre = 0 ans = 0 for i, x in enumerate(nums, 1): pre += x r = pre % k if r in first: ans = max(ans, i - first[r]) else: first[r] = i return ans这段代码里有几个点需要解释。第一，初始化first[0] = 0，对应空前缀的位置0。第二，只有当余数第一次出现时才记录位置，这样才能保证“当前位置减去首次出现位置”得到的差是“该余数类里最长的子数组”。第三，题目如果要求子数组必须非空，还要额外加个判断，确保长度大于0。
这个变种题完美诠释了桶优化的灵活性：桶的结构不变，桶里的“值”从计数变成了下标，解决的问题就完全不同了。这也提示我们，遇到新题不要僵化套模板，先想清楚题目到底要什么，再去决定桶里存什么。
4. 同余桶思想的更多战场：校验码、循环节与状态压缩
4.1 校验码里的同余：ISBN-10与mod 11/10
很多人以为同余和桶只存在于算法竞赛中，其实它在现实工程里应用特别广。最典型的就是ISBN-10书号的校验算法。
ISBN-10的规则是：前9位数字依次乘以10、9、8、…、2，得到一个加权和sum，然后计算校验位check = (11 - sum % 11) % 11。如果结果等于10，就用X表示。举例来说，假设前9位是0-306-40615，那么加权和是010 + 39 + 08 + 67 + 46 + 05 + 64 + 13 + 5*2 = 142，142 % 11 = 10，check = (11 - 10) % 11 = 1，所以校验位是1，完整书号是0-306-40615-1。
这个校验过程本质上就是“把一串数字压缩成一个模11的余数，再检查余数是否符合特定值”。你看，它和974题里“把前缀和压缩成模K的余数，再检查余数是否相同”是同一个思维模型。理解了这个，刷题时就多了一层亲切感：原来我们天天用的书籍编号，背后就是同余理论在支撑。
4.2 循环节、环形数组与同余分组
再往深走一层。只要数据存在“周期为K”的性质，同余分组就是天然优化方向。我做模拟题时遇到过很多“状态每走一步对M取模”的题，处理经验是：余数一旦出现重复，就意味着进入循环，后面一大段状态序列会周而复始地重复，可以直接跳过，不用一步步傻算。
环形数组问题也是如此。有人喜欢把数组复制一份来模拟环，其实可以直接用下标对数组长度取模来完成环形定位。本质上还是在用模运算处理循环结构。
同余分组的通用价值在于：它把“连续数值域”（比如前缀和的范围可能非常大）压缩成“离散的K个类”。数据一旦被分进K个同余桶里，后续的查重、计数、求最长距离、判断循环，都只发生在桶内部，和全局无关。这就是降维。
4.3 状态压缩里的同余判断
动态规划里同样大量出现同余。比如集合划分问题，要求判断能否把一些数分成若干组，每组和相等。如果总数对K有整除约束，余数往往直接可以作为DP状态的一维。再比如某些背包优化，枚举数量维度时可以按模K分成几个类，每个类内部单独做单调队列优化，从而把一维循环的复杂度降下来。
这类题型的共同点都是：表面上看不出“同余”两个字，但一旦你把数据按模K分类，规律就出来了。这就是为什么我一直强调，同余桶不只是“一道题的解法”，而是一种通用的算法直觉。当你看到整除、取模、循环、周期这几个关键词时，大脑就应该自动弹出“前缀和 + 同余 + 桶”的候选方案。
5. 常见问题与排查技巧实录
5.1 负数取模的跨语言差异
这是所有坑里出场率最高的一个。C++和Java对负数取模会保留负号，Python则保证结果和除数同号（所以除数为正时结果非负）。直接用语言默认的取模结果作为桶下标，是必错写法。
错误写法示范：
int r = pre % k; // 如果pre是负数，r可能是负数，访问数组越界正确写法：
int r = (pre % k + k) % k;再提醒一个点：如果K本身可能为负数，这个防御公式也救不了你。虽然题目一般给正整数K，但万一遇到，先把K取绝对值，再统一处理。
5.2 桶初始化漏掉pre[0]
第二个高频bug是忘了把pre[0] = 0对应的余数0在桶里初始化为1。这个初始化代表“空前缀”的存在。没有它，所有从数组开头开始且满足条件的子数组都会被漏统计。
我再用一个极小例子验证。nums = [5], K = 5，结果应该是1。如果不初始化cnt[0]，桶为空，扫到5时r = 0，ans += 0，答案是0，直接错误。初始化cnt[0] = 1后，ans += 1，答案正确。
工程上怎么避免这种错？建议把“前缀和桶”的初始化写成固定两步：先建桶，然后显式cnt[0] = 1。不管题目里数组是什么，这个步骤永远不省。
5.3 前缀和溢出与取模时机
数组元素很大、n也很大时，pre的累加值很容易超出int范围。两种处理方式：一是把pre声明为long long；二是只保留模K后的余数前缀。第二种有个前提，题目只关心余数之间的比较关系，比如974题。这里给出余数前缀的写法：
int r = 0; for (int x : nums) { r = ((r + x) % k + k) % k; // 用r做桶查询和更新 }因为(a + b) % k == (a % k + b % k) % k，所以这样维护出来的r和“先维护完整pre再取模”结果完全一致，还省掉了long long。但560题这类需要比较pre - K精确值的题目不能这么省，必须维护真实前缀和，否则信息丢失，答案必然错。到底用哪种，就一条判断标准：题目要的是余数关系，还是数值关系。
5.4 哈希桶的退化问题
最后聊下哈希桶的性能隐患。unordered_map在平均情况下是O(1)，但遇到数据构造不好的场景可能退化，尤其是K在2的幂附近，很多数值的低位高度重合时，桶内元素容易扎堆。竞赛中如果时限卡得很紧，这就是致命的。
我的应对策略是三级方案：第一优先数组桶，K允许就开数组；第二，如果K很大，但n不大，可以把所有余数记录下来，排序后统一统计，避开哈希的动态扩容和碰撞问题；第三，实在要用哈希表，就自己写一个简单可靠的哈希函数，或者直接换map，把时间稳定在O(n log n)。
前面提到的mod 11/10校验也是一个思路：校验算法往往用固定模数，不依赖动态哈希，所以性能和时间复杂度都可精确预估。做工程或者竞赛，稳定性永远排在第一位。
最后再分享一点个人体会。同余转化和桶优化这套组合，最值钱的地方是一套思维习惯：看到整除、取模、重复周期，立刻想到前缀和、余数分类、桶内聚合。我当年第一次接触974题时也觉得巧妙，但真正搞懂是在纸上把前缀和的每个余数列出来之后。那一刻我才发现，所有合法子数组其实就是那些“相同余数”之间的连线。希望你也能亲手做一遍这个推演，那个豁然开朗的瞬间，比背任何模板都值钱。
