和可被 K 整除的子数组

记住「同余即可整除:答案 += 该余数已出现次数,再让它 +1」,下面每帧都在套它。

开局把「余数 0 出现 1 次」放进表里——这代表「空前缀」，它让那些「从数组开头起就能被 k 整除」的子数组也能被正确数到。

读第 0 个 4，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 0 次——意味着前面有 0 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：余数 4 之前没出现过（加 0，答案仍 0）；把它记进表（现 1 次），等后面有相同余数再来配。

读第 1 个 5，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 1 次——意味着前面有 1 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：答案加上 1，变成 1；再把当前这个余数 4 记进表（现 2 次），供后面的元素配对。

读第 2 个 0，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 2 次——意味着前面有 2 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：答案加上 2，变成 3；再把当前这个余数 4 记进表（现 3 次），供后面的元素配对。

读第 3 个 -2，更新前缀和、对 5 取余得余数 2（表中高亮那行）。表里余数 2 已出现 0 次——意味着前面有 0 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：余数 2 之前没出现过（加 0，答案仍 3）；把它记进表（现 1 次），等后面有相同余数再来配。

读第 4 个 -3，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 3 次——意味着前面有 3 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：答案加上 3，变成 6；再把当前这个余数 4 记进表（现 4 次），供后面的元素配对。

读第 5 个 1，更新前缀和、对 5 取余得余数 0（表中高亮那行）。表里余数 0 已出现 1 次——意味着前面有 1 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：答案加上 1，变成 7；再把当前这个余数 0 记进表（现 2 次），供后面的元素配对。

读第 6 个 2，更新前缀和、对 5 取余得余数 2（表中高亮那行）。表里余数 2 已出现 1 次——意味着前面有 1 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：答案加上 1，变成 8；再把当前这个余数 2 记进表（现 2 次），供后面的元素配对。

读第 7 个 6，更新前缀和、对 5 取余得余数 3（表中高亮那行）。表里余数 3 已出现 0 次——意味着前面有 0 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：余数 3 之前没出现过（加 0，答案仍 8）；把它记进表（现 1 次），等后面有相同余数再来配。

读第 8 个 4，更新前缀和、对 5 取余得余数 2（表中高亮那行）。表里余数 2 已出现 2 次——意味着前面有 2 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：答案加上 2，变成 10；再把当前这个余数 2 记进表（现 3 次），供后面的元素配对。

读第 9 个 3，更新前缀和、对 5 取余得余数 0（表中高亮那行）。表里余数 0 已出现 2 次——意味着前面有 2 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。

结算：答案加上 2，变成 12；再把当前这个余数 0 记进表（现 3 次），供后面的元素配对。

全程扫完，累计答案 = 12。每一步都把「当前余数的历史出现次数」加进答案——同余配对，一遍 O(n) 就数清了，无需枚举所有子数组。

边界先想清:不被整除、全整除、含负数取模。

面试常把本题和 LC560 对比，认出「前缀和+哈希」母题即可。