【题解】P8649 题解

### P8649 题解 #### 思路分析 一道简单前缀和的题。 首先，看到”连续子序列求和”这一要求时，我们果断选择前缀和解答。 接着我们要分析，什么时候这段区间的和为 $K$ 的倍数？显然，当区间和 $\text{sum}$ 满足 $K \mid \text{sum}$，即 $\text{sum} \bmod k = 0$ 时，为 $K$ 的倍数。 而又由于原数组 $a$ 中 $a_l \sim a_{r}$ 的区间和 $\text{sum}$ 等于 $p_r - p_{l-1}$（$p$ 为 $a$ 的前缀和数组），所以 $p_r - p_{l-1} \equiv 0 \pmod k$。所以 $p_r \equiv p_{l-1} \pmod k$。 也就是说，我们只需判断前缀和模 $k$ 是否同余就可以了，但一个个枚举区间有点慢，怎么办呢？ 我们可以来一个“回手掏”，从”模 $k$ 同余“入手。我们可以开一个 map 记录每个前缀和模 $k$ 的余数出现的次数，然后在同余数的情况下，任选两个前缀和，必然能够构成一段区间，这段区间的和为 $K$ 的倍数。设某个余数出现了 $x$ 次，则必会存在 $\text{C}^{2}_{x}$ 段区间和为 $k$ 的倍数。 注意：map 要将余数 $0$ 出现的次数初始化为 $1$。这样的话，如果 $0$ 出现了 $x$ 次的话，则必会存在 $\text{C}^2_{x + 1}$ 段区间和为 $k$ 的倍数。为什么呢？因为，根据题意，一个数也算一段区间，即答案为： $$C^2_{x} + x = \dfrac{x(x-1)}{2} + x = \dfrac{x(x-1)}{2} + \dfrac{2x}{2} = \dfrac{x(x-1 + 2)}{2} = \dfrac{x(x+1)}{2} = \text{C}^2_{x+1}$$ 依据上述步骤实现即可，然后记得开 long long。 #### 代码 ```cpp #include <iostream> #include <map> #define int long long using namespace std; map <int, int> mp; //记录每个余数出现个数的数组 signed main() { int n, k, ans = 0; cin >> n >> k; mp[0] = 1; //初始化 0 出现的次数为 1 for(int i = 1;i <= n;i++) { int x; cin >> x; ans += (x % k); //计算前缀和 mp[ans % k]++; //前缀和模 k ans %= k; } int cnt = 0; for(int i = 0;i < k;i++) cnt += (mp[i] * (mp[i] - 1)) / 2; //根据上述公式计算答案 cout << cnt << endl; return 0; } ```