简单来讲，sum[r] % k 和 sum[l-1] % k 的余数如果相等，那么sum[r] - sum[l-1]的差值必然是k的倍数 ，比如说
13 % 7 和 20 % 7 (20-13)%7 =0；

妙啊 懂了

soga!!!!

解释下 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[sum[i]]个k倍让后呢

牛啊，突然就懂了，谢谢解答

一直更新区间最后就可以求出个数了啊

真是妙蛙种子吃着妙脆角，妙进了米奇妙妙屋 ，妙到家了

终于搞懂了

我有一个问题 按照例子来说 1 2 3 4 5 前缀和 1 3 6 10 15 那对k = 2 取模后为 1 1 0 0 1 前两个1组成一个区间 但是他们对应的是1 和2 这两个数加起来不是2的倍数呀 求解释

1和2 s[1]=1 s[2]=3 s[1]+s[2]=4

如果sum[i]==sum[j]成立的话,应该是[i+1,j]区间是k的倍数

如果感觉ans+=res[sum[i]];//更新答案不太好理解的同学，可以最后单独对res中的数据进行计算，即$C_n^2$，那么它的计算公式就是$n(n−1)/2$。
我们可以知道sum[i]在取模后中的最大值就是k−1，因此我们可以枚举到k−1，然后进行累加即可。
我的代码：

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

const int N = 1e5 + 10;
int a[N], s[N];
map<int, int> cnt; //同余的个数

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    cnt[0] = 1; 
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = (s[i-1] + a[i]) % k; //前缀和优化
        cnt[s[i]]++;
    }
    long long res = 0;
    for(int i = 0; i < k; i++) { //余数必然在0~k-1之间
        res += (long long)cnt[i] * (cnt[i] - 1) / 2;
    } 

    printf("%ld", res);
    return 0;
}

这个思路太可了

res还要加上cnt[0]，因为$C_n^2$就是要选两个前缀和相减，这样就选不到子序列包含A[0]的情况，而这种情况的个数就是cnt[0]

对啊 我前边cnt[0] = 1已经考虑到了

cnt[0] = 1； 这句是不是没有用？（我没用它也AC了）

赞！

关于预先处理cnt[0]=1我的理解，因为对k取余==0的前缀和即说明本身就是k的倍数，比如取余结果是0的有3个，假设k=2，那三个数是4，6，8，如果不预处理cnt[0]=1，那么cnt[0]=3，但你不能说k倍区间有C3取2=3，显然不止，4，6，8本身也是一个k倍区间，所以应该是6个，所以预处理cnt[0]=1，结果就是cnt[0]=4，即C4取2=6

我试了下要有才能ac

没有偶数的时候C(2,1)=0
有一个偶数的时候C(2,2)=1
处理该数字本身就是k的倍数的边界情况 如果没有就n*(n-1)/2 ==0 只有含有自身为k倍数的时候才能发挥作用

这种做法必须要用map存储每一个余数个数，如果用数组就会出现结果比实际要小，亲身体会

那倒不是 比实际结果小的原因是你可能忘了加cnt[0] = 1 对k取余为0的本身就是一个k被区间 每次配对 都要多相应的个数 我用数组也一样ac了

答主这个代码很精简但是不易读本质就是cn2然后对每一个余数单独计算就行，但是用累加其实也可以因为这个就代表每一次前面那些数的出现次数类比于也是1+2+3+。。。。+n

我就这样的哈哈

妙啊

经过痛苦的漫长的思考，我终于是明白了为什么要加res[0]

对样例的理解

a 1 2 3 4 5

s[i] 1 3 6 10 15

s[i]%k 1 1 0 0 1

这时，同余的情况一共有4种

（1,1) (1,1) (1,1) (0,0)

此时是res[s[i]]=4

而单个s[i]%k==0依然是满足题意的

也就是那两个0 res[s[i]]+res[0]=6

相通之后真的很简单，相通之前真的很痛苦

希望对大家能有一点帮助

理解了，谢谢

在深入解释下：

1.首先，cnt[0] 的初值是0，当遍历到前缀和为6的时候，ans先加上cnt[6 % 2] 即 cnt[0]，ans并没有改变，也就是此时漏加了一种情况，之后才有cnt[6 % 2] ++，注意，此时cnt[0]加1了，所以最后我们结算答案的时候，加上cnt[0]，也即是加上了我们在遍历过程中漏加的余数为0的，也即[1, i]前缀和为0的K倍区间。

2.对于首先给cnt[0] = 1赋初值，实际上是上文说的情况等价的，就是在结算过程中，保证不漏加。

不知道理解对不对
res的值 仅统计 相同余数 的对数 余数相同且为0时 是特殊情况

谢谢哥 讲解的真好！

我有一个问题 按照例子来说 1 2 3 4 5 前缀和 1 3 6 10 15 那对k = 2 取模后为 1 1 0 0 1 前两个1组成一个区间 但是他们对应的是1 和2 这两个数加起来不是2的倍数呀 求解释

前两个1代表的是s[1]和s[2]，前两个1组成的区间实际上是s[2]-s[1]这个区间，也就是a[2]

梳理一下小白理解思路
输入数组->求前缀和对k取余的余数 //因为要筛选出满足sum右%k-sum左 %k==0的余数
然后ans+=res[sum[i]]是把这个余数放入考虑的集合(初始时候为0 放进去之后res[sum[i]]+1)并和集合中相同的余数组合出新的组合 加上增加的数量 (可以认为新余数是和现有的相同余数连线 线的的数量等于现存余数数量)
然后最后还要考虑余数0本身就可以满足%k==0而不需要另外一个0与其组合 所以ans加上res[0] 得到答案ans

谢谢了，终于明白为什么res[0]是1了

(sum[i]-sum[j])%k=0分配率得：sum[i]%k-sum[j]%k=0

想到了一个解释方法，ans一开始是表示的相减满足题目的条件，因为一旦再出现%k和res数组里面有相当的情况，就全加一遍（和前面全部组合一遍），然后res【sum【i】】++；最后考虑不用相减直接就可以满足条件的情况，就是%k = 0；直接加res【0】就可以了，（和后面组合余数为0的情况相减的时候已经考虑过了）

谢谢你 明白了😘

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int n, k;
int a[N], cnt[N]; //cnt[i] 是余数为i的数的个数
long long s[N];
long long res;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }

    for (int i = 1; i <= n; i++)
    {
        res += cnt[s[i] % k]; //在这个数之前每个和它余数相同的数都能和它组成一个区间
        cnt[s[i] % k] ++;

        //注意，如果前缀和的余数为0的话说明开头到它本身的这些数就是一个区间
        if (s[i] % k == 0) res++;
    }

    printf("%lld\n", res);

    return 0;

}

这个是真的好理解

对前缀和取模，若sum[i] == sum[j]，那么区间[i + 1] j]的和必然是k的倍数。所以用cnt数组统计前面有几个这样的模即可。但是要注意左端点是i+1，最后的答案要重新加上i=0处的情况。
举个例子，
数字为 1 2 3 4 5，k = 3
前缀和 1 0 0 1 0
cnt[0]表示的是[1, 2][1, 3][1, 5]的情况

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
int n, k, a[N], cnt[N];
ll ans;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = (a[i] + a[i - 1]) % k;
        ans += cnt[a[i]];//加上区间[1, i - 1]内模为a[i]的前缀和个数
        ++cnt[a[i]];
    }
    cout << ans + cnt[0];//cnt[0]表示区间[1, n]内，以1为左端点的区间和，对k取模为0的数量；
    return 0;
}

cnt［0］的数量一直在ans中+啊，为啥最后还要加上cnt［0］啊?

你可以把每次遍历到的cnt[0]打印出来，或者自己举个简单的例子手动模拟一下。要么cnt[0]初始化为1，答案不用额外加上cnt[0]，要么初始化为0，答案额外加上。

其实cnt[0]初始化为1更合理一点，也更容易理解。在0处的模为0，后面第一次出现模为0的情况，就表示[1，pos]的和为k倍

谢谢 佬qaq ，我自己想一下

最后加上的cnt[0]是i=j的情况

因为前面加的是0和0的组合，就像1和1的组合，前面的逻辑是每次只有相同的数出现才会加1，但是，有些本身就是%k==0的，需要另外单独加上

终于理解了这道题了，没想到前缀和还能这么用

有没有对这里 取模运算 的 证明 呢？

后续会补上~

已经证明完毕，根据模运算的结合律：
(a+b) % p = (a%p + b %p) %p
(a%p + b) % p = (a%p%p + b %p) %p = (a+b) %p,
同理可得：
(a+b+c) %p = ((a%p + b) %p + c) %p
扩展开来，同上证明。

可 QAQ hhh

题解相应部分已完善！

秦九韶算法

res是用来计相同数构成的区间的，而在求余后的sum本来就是记录一个数组的求余内容，所以当其为0时，也是一个满足条件的区间。所以需要res 0 =1

res[]数组感觉就是并查集的思想吧

加res[0]是因为漏算了一个数作为区间的情况，例如当k=2，%k = 0时，ans只能计算[2,4],[2,6],[4,6]，而不能计算[2,2],[4,4],[6,6]这种以自身为一个区间的特殊情况，其实改成res[0] = 1要好点。

感觉你这个比Y总的好理解。Y总那个我现在也没理解为什么要那么做hh

$ans+res[0]$可以一开始直接把$res[0]$设为$1$，这个$1$代表的是什么都不取，也就是第$0$项的前缀和
我的代码：

#include<bits/stdc++.h>
using namespace std;
long long n,k,a,s,q[100009]={1},ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;++i) cin>>a,++q[s=(a+s)%k];
    for(int i=0;i<k;++i) ans+=q[i]*(q[i]-1);
    return cout<<(ans>>1),0;
}

这不是DP的思想么QAQ

为什么要加res[0]啊，有点不明白

这个是一个特殊情况，就是当res[r]=0的情况，其区间[0，r]就有(sum[r]-sum[l-1])%k == (sum[r])%k,因为这个ans更新是对于sum[r],前面有多少个是相等的sum[l-1]

还是不太明白~

ans 是成对出现的次数 res[0] 是 0 单独出现的次数
比如取模后 1 1 0 0 1
1 1
1 1
1 1
0 0
0
0
一共六个。

就是s[r-1]=0 区间和为s[l]？

res[0]是不是区间长度为1的个数啊

想了很久 不知道自己的想法对不对 就是循环枚举时对于右端点r，如果r前面某个数 l 满足s[r]和是s[l]同模时，则区间 [l+1,r]满足要求。当sr==0那么区间 [1,r] 满足要求，但是此时并不需要再从r 前面找左端点；如果要找左端点的话，比如前面的 l 也满足 s[l]（求模后）==0，我们得到的区间是[l+1,r]，由于i>=1(数组下标从1开始存储前缀和)，因此不会得到区间[1,r]（如果满足条件的话）的情况，因此需要单独拿出来再相加。这种特殊情况相当于确定了右端点r后，找到了从1到r满足条件的整段区间，而其他情况都是找到模相同的左端点l，然后剔除1到l的数后的另一部分区间才为所求区间。

就是单纯的前缀和，不是部分和

看了半天文字解释没懂res[0]，还是老哥你这例子好啊

就是之前找到的是两个 区间的 mod之后相同的值，但是对于 mod == 0区间 我可以不用找另外区间，我本身就是符合 mod k == 0 这个条件，循环里统计的时候没有考虑这个情况，所以之后要再加上

给你点个赞👍清晰

厉害

老哥谢谢翻了一圈终于明白了，新年快乐！

%%%%

我也疑惑这一点

太清晰了！点赞！

终于懂了！

两个相等的前缀和组成一个k倍区间就是s[r] = s[l-1]对吧，然后通过%k找0和1的叠加个数，ans记录个数

enen

应该不是两个相同前缀和 而且两个%k 相等的前缀和

应该是 s[r] >s[l-1] ，s[r]%k==s[l-1]%k , 麻烦您能详细的解释说明一下吗？ 还是不太懂

感谢懂了

评论里那个字母哥的代码里面初始化cnt[0]=1是因为他和别的所有数都不一样,别的所有数在没计算前缀和之前的cnt都是0,但是啥也不选也算一种,也就是cnt0初始就有一种,所以cnt[0]初始化为1.
本篇攻略也是一个意思,因为前缀和从1开始,所以res[0]天然就少了一种,少的这种就是每个数都单独算一个k倍区间,这也是因为零特殊,因为别的数比如余数为2的前缀和,他自己不能算一个区间,必须要找别的另外一个数组合成一个k倍区间,但是零不一样,零自己就是余数为零的区间.所以最后如果按选两个前缀和相减这种做法的话,实际相当于前缀和sum[0]和所有的余数为零的sum[i]都组合一次