题目链接： AcWing 1230 K倍区间
题意： 给定一段数列和一个整数$K$，假若其中的一段数之和是$K$的倍数，则称这段区间为$K$倍区间，问这段数列有多少个$K$倍区间
解题思路：
- 首先，对于这种求一个数列某一段和的问题，显然用到前缀和的处理方法
- 第二个需要解决的问题就是如何确定某一段数能不能被$K$整除，能够被$K$整除，意味着余数为$0$，所以一段数与$K$取模得$0$就说明这段数是要找的$K$倍区间
- 可以从前往后枚举，设当前枚举到第$i$位，且它的前缀和$sum[i]$与$K$取模为$m$，如果在$i$之前的第$j$位前缀和同样是与$K$取模得$m$的话，$sum[i]-sum[j]$也就是$A_{j+1}\dots A_i$这段数与$K$取模为$0$，这一段就可以计入答案了，对于任意一个$i$，只需要统计前面有多少个这样的$j$即可
- 具体的做法就是开一个计数数组$cnt[]$，$cnt[i]$就是计算余数为$i$的前缀和有多少个
- 另外要注意一点是，假如某一段数$A_1\dots A_i$，不需要减去区间，它本身就是一个$K$倍区间，但$cnt[0]$保存的是$i$之前余数为$0$的前缀和的个数，这个区间本身没有被算进去，所以初始状态下，$cnt[0]$应该赋值为$1$
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, k, cnt[N], sum[N];
LL ans;
int main() {
cnt[0] = 1;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &sum[i]);
// 数很大，要不断取模，事实上影响能否整除这一性质的只有余数，所以保存取模的结果即可
sum[i] += sum[i - 1] % k;
// 找前面有多少个j
ans += cnt[sum[i] % k];
// 对于当前这个i要计数
cnt[sum[i] % k]++;
}
printf("%lld\n", ans);
return 0;
}
```
%%%
感激，终于弄懂了，你的思路太过清晰
谢谢hh～
tql 怎么想出来的啊 666
这是一个很常用的思路。
我只能想到暴力hh
看了好几个题解，看博主的终于看懂了，666
加油hh~
感谢博主思路，我想了两个小时，终于明白了！/(ㄒoㄒ)/~~
加油hh～
果然还是转换不了数学意义和电脑语言- -谢谢Up
不客气hh～
假设s0存在，那么我们就可以找到(s0,s3) (s0,s4) 这两种缺的组合了 是这样吗
是的，这个做法是为了不漏掉从$1$开始的序列。
1 1 0 0 1->(1,1)(1,1)(1,1)(0,0)四种，然后为什么赋值为1就能补回去找一个长度的区间个数
懂了一点，我思路是错的。
这道题的思路是，找两个序列的modk之后的值相等，而我们不找两个序列的时候，就是单个序列时候也是成立的。
就如样例中单个长度的2、4,这里有两种，所以如果去掉cnt[0]=1答案就会少两个。
半懂，就是为啥cnt[0]为啥一定要等于1呢
而不是等于其他数？
求教，s[0]是0个数的和，为什么cnt[0]要被赋值？题目是把空集也当作一个K倍区间吗
知道了，i=a%c<c , j=b%c<c, i-j<c，故.. 打扰了
没事hh~
对前缀和取模之后，两个相等的前缀和就能组成一个k倍区间的结论是怎么得出的？
sum[i] += sum[i - 1] % k;
还是不太理解这个，为什么要在计算前缀和的时候要进行模运算
首先如果不取模的话，显然会爆
int的范围，虽然确实可以用long long去存，但分析之后可以发现，一个区间如果可以是K倍区间的话，就意味着这段区间的和能够整除$K$，换句话说，只需要这段区间和对$K$取模为$0$即可对吧，所以这个问题就可以转换一下，从处理和的问题转化为处理余数的问题，处理出来的结果是一样的，但后者处理的范围显然大大减小。所以在处理前缀和的时候，一样地，也只需要考虑前缀和的余数就行了。
~知道啦，蟹蟹；
感觉就是前缀和模k前后，他们最后到cnt中间去取模操作时，同样能得到一样的结果，所以像你这样先取模就还可以省去一个爆int的风险
对的，而且问题的处理范围大大减小，可以用$cnt$数组来对余数进行计数
嗯~ o(￣▽￣)o~ 才学算法，接触到新东西总会犯迷糊
一起加油hh~