cnt[i],表示余数是i的数有多少个
解释下 ans+=res[sum[i]];
首先明确 res[sum[i]] 表示的是sum[i]出现过的次数。
举个例子,假设 sum[i] = 3,在后边的循环中,又出现了一个 sum[i] = 3,那么此时,这个“3”可以和前边出现过的所有的“3”分别构成一个K倍区间,前边的“3”一共出现过res[sum[i]] 次,所以 此时又新增了res[sum[i]]个K倍区间。
为什么res要加上每个cnt[s[i] % k]?
当前s[i] 与前面cnt[s[i] % k]个区间相组合仍然为k倍区间 故res要加上每个cnt[s[i] % k],
随后改变cnt[s[i] % k] 的值即cnt[s[i] % k]++
关于cnt[0] =1的初始化:
s[0] = 0, 而0%任何数都是0,所以cnt[0] = 1。
i从右端点开始枚举,就需要比较左边从s[0]到s[i-1]这些数与s[i]同余与k的个数,右端点需要从1开始枚举,那么注意cnt[s[0] % k] 事实上没有被加上,在样例中的体现就是漏掉了序列【1,2,3】和【1,2,3,4】这两段序列,其前缀和为6和10
总结:若不进行该初始化,那么在以第i个数为右端点时,区间[a1,…,ai]这个区间的和若%k等于0,那么该区间会被漏掉。
cpp code
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1000001;
int N, K, a;
long long int s[MAX];
int cnt[MAX];
int main(){
cin >> N >> K;
for(int i = 1; i <= N; i ++ ){
int al;
scanf("%d\n", &al);
s[i] = s[i - 1] + al;
}
long long int ans = 0;
cnt[0] ++ ;
// for(int i = 1; i <= N; i ++ ){
// for(int j = i; j <= N; j ++){
// a = s[j] - s[i - 1];
// if(a % K == 0)ans++;
// }
// }
for(int i = 1; i <= N; i ++ ){
ans += cnt[s[i] % K];
cnt[s[i] % K] ++ ;
}
cout << ans << endl;
return 0;
}