蓝桥杯每日一题汇总
先求一遍前缀和,然后将前缀和全部 $\\% k$,然后从头往后枚举前缀和数组,假设当前枚举到 $s_i$,那前面有多少个和 $S_i$(此时 $S_i$ 已经取模过了) 的值相同的,就有几组答案。因为假设有一个区间 $l$ 到 $r$,那么 $(S_r - S_{l - 1}) \\% k = 0$,换句话说就是 $S_r \\% k = S_{l - 1} \\% k$。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
LL s[N], cnt[N]; // s 存前缀和,cnt 存 s 取模后每种可能的结果各出现了多少次
LL res;
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i ++) {
cin >> s[i];
s[i] += s[i - 1];
}
/*
这里把 cnt[0] ++ 的原因是 k 倍序列里可以从头到 i 组成,
比如样例中的 s 取模后是 1 1 0 0 1,
s[3] = 6, s[4] = 10, 都可以构成 k 倍序列。
但我们是要找两个序列互相消除,比如一个组合 (1, 2), s[2] - s[1] = 2, 另一个组合 (3, 4), s[4] - s[3] 4。
所以 cnt[0] 就得先被 + 1次,否则 s[3] % 2 = 0,但是前面 cnt[0],没有加一,导致漏了一个答案
*/
cnt[0] ++;
for (int i = 1; i <= n; i ++) {
res += cnt[s[i] % k];
cnt[s[i] % k] ++;
}
cout << res << endl;
return 0;
}