你好！很高兴能以OI竞赛教练的身份为你讲解这道经典题目。

这道题在LeetCode上是974题，但在NOIP、CSP-S或蓝桥杯等竞赛中，这是前缀和与同余性质结合的教科书级例题。

---

一、 题目描述：和可被 K 整除的子数组

题目名称： 和可被 K 整除的子数组 (Subarray Divisibility) 时间限制： 1.0s 空间限制： 256MB

题目背景

小明正在研究整数序列的性质。他发现有些连续子序列的和非常特殊，能够被给定的整数 $K$ 整除。

题目描述

给定一个由 $N$ 个整数组成的序列 $A = \{a_1, a_2, \dots, a_N\}$ 和一个整数 $K$。 请你计算该序列中有多少个非空连续子序列（Subarray），其元素之和能够被 $K$ 整除。

形式化地，你需要找到满足以下条件的二元组 $(i, j)$ 的数量：

1. $1 \le i \le j \le N$
2. $( \sum_{x=i}^{j} a_x ) \bmod K = 0$

输入格式

第一行包含两个整数 $N$ 和 $K$。 第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，表示序列中的元素。

输出格式

输出一个整数，表示满足条件的连续子序列的数量。

数据范围

• 对于 $30\%$ 的数据，$1 \le N \le 100$。
• 对于 $60\%$ 的数据，$1 \le N \le 1000$。
• 对于 $100\%$ 的数据，$1 \le N \le 10^5, \quad 2 \le K \le 10^4, \quad -10^4 \le a_i \le 10^4$。
• 注意：最终答案可能超过 32 位整数范围。

四、 样例数据 (Sample Data)

样例输入 #1

6 5
4 5 0 -2 -3 1

样例输出 #1

7

样例输入 #2 (边界测试：全负数与整除)

5 9
-9 -18 -27 -36 -45

样例输出 #2

15

样例说明 (Hint)

针对样例 #1 的解释：

我们需要寻找连续子数组的和能被 $K=5$ 整除的情况。 数组 $A = [4, 5, 0, -2, -3, 1]$。

我们可以列举出以下 7 个符合条件的子数组（下标从 1 开始）：

1. $[5]$ (下标 2)，和为 5，能被 5 整除。
2. $[5, 0]$ (下标 2~3)，和为 5，能被 5 整除。
3. $[5, 0, -2, -3]$ (下标 2~5)，和为 0，能被 5 整除。
4. $[0]$ (下标 3)，和为 0，能被 5 整除。
5. $[0, -2, -3]$ (下标 3~5)，和为 -5，能被 5 整除。
6. $[-2, -3]$ (下标 4~5)，和为 -5，能被 5 整除。
7. $[4, 5, 0, -2, -3, 1]$ (下标 1~6)，和为 5，能被 5 整除。

教练的点拨（利用前缀和余数）： 如果我们计算前缀和对 5 取模（注意负数修正），序列会变成： [0(初始), 4, 4, 4, 2, 4, 0] 可以看到：

• 余数为 0 出现了 2 次 $\rightarrow$ 贡献 $C_2^2 = 1$ 个答案。
• 余数为 4 出现了 4 次 $\rightarrow$ 贡献 $C_4^2 = 6$ 个答案。
• 余数为 2 出现了 1 次 $\rightarrow$ 贡献 0 个答案。 总计 $1 + 6 = 7$。这比上面的暴力枚举快得多！

---

六、 数据范围与约定 (Data Scale)

为了考察大家的算法优化能力，本题设置了梯度数据：

• 对于 30% 的数据：$N \le 100$。
  • 提示： $O(N^3)$ 或 $O(N^2)$ 的暴力算法可以通过。
• 对于 60% 的数据：$N \le 1000$。
  • 提示： $O(N^2)$ 的算法可以通过。
• 对于 100% 的数据：$1 \le N \le 30,000$ (注: LeetCode原题较宽松，竞赛常会卡紧一点，这里按 $10^5$ 准备更稳妥)，$2 \le K \le 10,000$。
  • 元素值域：$-10,000 \le a_i \le 10,000$。
  • 提示： 必须使用 $O(N)$ 的前缀和+同余桶优化算法。
  • 坑点预警： 最终答案可能会超过 32 位整数（int）的范围，请务必使用 64 位整数 (long long) 存储答案。

---

二、 预备知识点总结

在解决这道题之前，你需要掌握以下“武器”：

1. 前缀和 (Prefix Sum)： 快速计算区间和的基础。$S[i] = a_1 + \dots + a_i$。区间 $[i, j]$ 的和可以表示为 $S[j] - S[i-1]$。
2. 同余模运算 (Modular Arithmetic)：
   • 同余性质：如果 $A - B$ 能被 $K$ 整除，即 $(A - B) \equiv 0 \pmod K$，那么 $A \equiv B \pmod K$。
   • 负数取模（C++坑点）： 在 C++ 中，负数取模的结果是负数（例如 -5 % 2 = -1），但在数学同余类中我们需要正余数。修正公式为：((x % K) + K) % K。
3. 组合计数 / 桶思想 (Frequency Array)： 利用数组或哈希表记录某个状态出现的次数，从而快速计算组合数。

---

三、 启发式教学：草稿纸上的推理演练

好，同学们，现在拿起笔，我们在一张白纸上把思路画出来。

1. 朴素思路（暴力法）

首先，最直观的做法是什么？ 枚举所有可能的起点 $i$ 和终点 $j$，算出和，看能不能整除 $K$。

$$\text{Sum}(i, j) \% K == 0$$

• 枚举 $i$ 和 $j$ 需要 $O(N^2)$。
• 如果没用前缀和，内部求和还要 $O(N)$，总共 $O(N^3)$。
• 用了前缀和是 $O(N^2)$。
• 思考： 看一眼数据范围 $N=10^5$，计算机一秒大概跑 $10^8$ 次运算，$N^2$ 就是 $10^{10}$，绝对超时 (TLE)。我们需要 $O(N)$ 的解法。

2. 转化问题（利用前缀和）

我们要找的是区间 $[i, j]$ 的和能被 $K$ 整除。用前缀和数组 $S$ 表示：

$$(S[j] - S[i-1]) \% K == 0$$

让我们把等式变换一下（利用同余性质）：

$$S[j] \equiv S[i-1] \pmod K$$

这是解题的关键！ 这句话翻译成人话就是：只要两个位置的前缀和，它们对 $K$ 取模后的余数相等，那么这两个位置中间夹的那段子数组的和，一定能被 $K$ 整除。

3. 模拟演练（画图理解）

假设 $N=6, K=5$，数组 $A = [4, 5, 0, -2, -3, 1]$。 我们来一步步算前缀和 $S$，以及前缀和对 $K$ 取模的值 Mod。

索引 $x$	0 (初始)	1	2	3	4	5	6
元素 $A[x]$	-	4	5	0	-2	-3	1
前缀和 $S[x]$	0		9		7	4	5
余数 $S[x] \% 5$		4			2	4	0

注意：索引0是我们虚拟加入的，代表“一个元素都没选”的状态，和为0。

观察草稿纸：

• 我们看到了好几个余数为 4 的位置：索引 1, 2, 3, 5。
  • 选索引 1 和 2 ($S[2]-S[1]$)：区间 $A[2]$ (5) -> $5\%5=0$。对！
  • 选索引 1 和 3 ($S[3]-S[1]$)：区间 $A[2..3]$ (5, 0) -> $5\%5=0$。对！
  • 选索引 1 和 5 ($S[5]-S[1]$)：区间 $A[2..5]$ (5, 0, -2, -3) -> $0\%5=0$。对！
• 如果有 $M$ 个位置的余数相同，我们可以从中任选 2 个点作为 $i-1$ 和 $j$，都能组成一个合法子数组。这不就是组合数 $C_M^2$ 吗？或者我们在遍历时，直接看“前面有多少个跟我余数一样的”，加到答案里即可。

4. 处理负数（避坑指南）

看索引 4：$S[4] = 7$。 看索引 5：$S[5] = 4$。 如果数组里有负数，比如前缀和是 $-1$，$K=5$。 C++: -1 % 5 = -1。 我们希望它归类到余数 4 的桶里（因为 $-1 \equiv 4 \pmod 5$）。 公式： remainder = (sum % K + K) % K。

5. 算法流程图解

我们需要一个桶（数组 cnt），大小为 $K$，用来存每个余数出现了几次。初始化 cnt[0] = 1（代表前缀和为0的情况出现了一次）。

遍历数组 $x$ 从 1 到 $N$：

1. 更新当前前缀和 sum += A[x]。
2. 计算规范余数 rem = (sum % K + K) % K。
3. 查询： 之前出现过几次这个 rem？（即 cnt[rem] 的值）。把这个值加到最终答案 ans 中。
   • 解释：当前位置 $x$ 可以和之前所有出现过 rem 的位置分别组成一个合法区间。
4. 更新： 把当前这个 rem 记录下来（cnt[rem]++）。

四、 复杂度分析

• 时间复杂度： 我们只需要遍历一次数组，每次操作都是加减模运算和查表，是常数时间。所以总时间是 $O(N)$。这对于 $N=10^5$ 来说绰绰有余。
• 空间复杂度： 我们需要一个大小为 $K$ 的数组来记录余数出现的次数。所以空间是 $O(K)$。题目中 $K \le 10^4$，非常小，完全没问题。

优化建议： 对于 OI 选手，使用 std::map 虽然方便，但有 $O(\log K)$ 的开销且常数大。既然 $K$ 的范围已知且较小，直接使用数组 int cnt[K] 是最高效、最稳妥的写法。

---

五、 读题关键词总结

做这类题时，当你看到以下关键词，DNA里要立刻产生反应：

1. “连续子数组” / “子串” (Subarray/Substring)：
   • 反应：大概率和前缀和有关，或者是滑动窗口。
2. “和能被 K 整除” / “和为 K 的倍数”：
   • 反应：同余。$S[j] \equiv S[i] \pmod K$。
   • 如果是“和为 K”，则是 $S[j] - S[i] = K \Rightarrow S[i] = S[j] - K$（两数之和问题）。
3. “负数”：
   • 反应：取模时小心负数，必须用 (a % k + k) % k 修正。

---

六、 OI风格参考代码 (C++14)

/**
 * 题目: 序列整除 (Subarray Sums Divisible by K)
 * 来源: LeetCode 974 改编
 * 算法: 前缀和 + 同余模运算 + 计数桶
 * 时间复杂度: O(N)
 * 空间复杂度: O(K)
 */

#include <bits/stdc++.h>

using namespace std;

// 使用 long long 以防万一，虽然题目中 cnt 不太可能爆 int，但 ans 可能爆
typedef long long ll;

const int MAXK = 10005; // 根据题目 K <= 10000

// 全局变量定义，防止栈溢出，且自动初始化为0（对于 cnt 数组）
int cnt[MAXK]; 

int main() {
    // 1. OI 必备：关闭流同步，加速 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    if (cin >> n >> k) {
        // 2. 初始化
        // 清空计数数组（如果是多组数据测试，这一步很重要，这里单组其实全局已初始化）
        memset(cnt, 0, sizeof(cnt));
        
        // 核心：前缀和为0的情况初始算出现1次（处理从头开始的子数组）
        cnt[0] = 1;

        ll ans = 0;
        int current_sum = 0; // 当前前缀和
        
        for (int i = 0; i < n; ++i) {
            int val;
            cin >> val;
            
            // 更新前缀和
            current_sum += val;
            
            // 3. 计算余数，核心修正公式处理负数
            // C++中 -5 % 2 = -1, 我们需要的是 1
            int remainder = (current_sum % k + k) % k;
            
            // 4. 统计答案
            // 如果之前有 cnt[remainder] 个位置的前缀和模 k 也是 remainder
            // 那么当前位置可以和那 cnt[remainder] 个位置分别组成一个合法子数组
            ans += cnt[remainder];
            
            // 5. 将当前状态存入桶中
            cnt[remainder]++;
        }
        
        cout << ans << endl;
    }

    return 0;
}

希望这份辅导资料能帮你彻底吃透这道题！记得在草稿纸上多画几个负数的例子，加深对“负数取模修正”的理解。加油！