C++ 代码
/*
前缀和我们都会,但能想到去转换进而发现规律的我想很少,hh(本身菜的原因)
eg: 求 L ~ R 这个区间的前缀和, sum[R] - sum[L - 1]
回到题目中,我们发现 (sum[R] - sum[L - 1]) % k == 0 说明这个区间是 K 倍区间
sum[R] % k == sum[L - 1] % k
这就说明如果前缀和 mod k 相同的话说明这个区间是 K 的倍数.
拿样例来说:
5 2
原数据:1 2 3 4 5
前缀和:1 3 6 10 15
mod k :1 1 0 0 1
个数 :0 1 0 1 2
我们发现 mod k 之后得到的 1 的个数为 3 个,所以可以组成的区间是 1 ~ 2,1 ~ 5,2 ~ 5;
结论:mod k 后相同的值将进行组合,为了避免重复计算,之后遇到相同的值,只需要进行累加
由于 0 比较特殊,也就是除了mod k 后相同的值 0,还有 1 ~ 这个值,也是一个合理区间,只
需要在最后 + 上 即可
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<string>
#include<cstdio>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long LL;
LL sum[maxn],res[maxn];
int n,k,value;
LL ans; // 次数用 long long,(谨记)
int main(void) {
scanf("%d%d",&n,&k);
ans = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d",&value);
sum[i] = (sum[i - 1] + value) % k;
ans += res[sum[i]]; // 由于数组初始化为 0 ,所以可以直接先 +
res[sum[i]] ++;
}
printf("%lld\n",ans + res[0]);
return 0;
}
你好,你的注释里面 //由于 0 比较特殊,也就是除了mod k 后相同的值 0,还有 1 ~ 这个值// 1~ 这个值 ------指的是什么呀