题目描述

给定一个长度为$ N $的数列，$A1,A2,…AN$，如果其中一段连续的子序列 $Ai,Ai+1,…Aj$ 之和是 $K$ 的倍数，我们就称这个区间$ [i,j] $是 $K$ 倍区间。

你能求出数列中总共有多少个 $K$ 倍区间吗？

输入格式

第一行包含两个整数 $N$ 和$ K$。

以下 $N$ 行每行包含一个整数$ Ai$。

输出格式

输出一个整数，代表 $K $倍区间的数目。

数据范围

$1≤N$,$K≤100000$,
$1≤Ai≤100000$

输入样例

5 2
1 2 3 4 5

输出样例

6

个人思路(自己也是想了许多时间、看了许多大佬的题解才想明白的，其实只要自己模拟模拟、举个列子看看就一定会明白的。要是没想通大家可以看看下面的例子和模拟呀^_^)：

(1)首先肯定是用前缀和数组$s[]$，而对于过分大的数字两层循环会超时，因此还得优化到一层循环。

(2)分析可得若求某一个区间的和，就是$s[r]-s[l-1]$。而若某个区间满足$k$倍区间,
就一定满足$(s[r]-s[l-1])$%$k$==$0$,然后化解就是$s[r]$%$k$==$s$[$l-1]$%k。

(3)此时，计算完前缀和数组后，用一个$cnt[n]$数组(其中$cnt[i]==1$表示前缀和数组中对$k$取模余数是$i$的前缀和有$1$个)来记录有多少个前缀和他们取模之后是一样的数字。

(4)从前往后循环，每次记录前缀和取模之后的数据，也就是$cnt[s[i]$%$k]$，往后循环一次，先看前面有无和该前缀和取模之后数字一样的前缀和，有$1$个一样的则答案$+1$、$2$个答案$+2$···；随后记得每次把$cnt[s[i]$%$k]++$。

注意

还得把$cnt[0]$赋值1，因为没有计算$0$%$k==0$这一项。

举例

$A1$~$A5$:$1，2，3，4，5$。$k$是$2$。

前缀和是：$1，3，6，10，15$；

前缀和对2取模$cnt[1$~$5]$数组：$1，1，0，0，1$；

而直观看的话，1~5的2倍区间是：$1$~$3，1$~$5，2，2$~$5，3$~$5，4$这么6个区间.

那么观察前缀和对2取模的数组:如果$cnt[i]$和$cnt[j]$相等，那么$A（i+1）$~$Aj$就是一个2倍区间。

比如$cnt[1]==cnt[2]$,那么$A2$~$A2$就是一个$k$倍区间；$cnt[1]==cnt[5]$,那么$A2$~$A5$就是一个$k$倍区间。

模拟

就拿$1，2，3，4，5$，$k=2$模拟吧：(注意都是从1开始计数的)
(1)$a[1]=1$，$a[2]=2$, $a[3]=3$, $a[4]=4$, $a[5]=5$;

(2)首先计算前缀和数组：$s[1]=1$, $s[2]=3$, $s[3]=6$, $s[4]=10$, $s[5]=15$;

(3)然后记得把$cnt[0]=1$;

(4)从$1$开始循环，一直到$5$；

(5)开始循环：
①第一项$s[1]=1$，有$s[1]$%$2==1$;而$cnt$数组中$cnt[1]==0$,因此么的答案，res==0；然后$cnt[1]==1$,
②第二项$s[2]=3$，有$s[3]$%$2==1$；$cnt$数组中$cnt[1]==1$，因此res=res+1=0+1==1；然后$cnt[1]==2$;
③第三项$s[3]=6$，有$s[3]$%$2==0$；$cnt$数组中$cnt[0]==1$（一开始把$cnt[0]=1$），因此res=res+1=1+1==2；然后$cnt[0]==2$;
④第四项$s[4]=10$，有$s[4]$%$2==0$；$cnt$数组中$cnt[0]==2$，因此res=res+2=2+2==4；然后$cnt[1]==2$;
⑤第五项$s[5]=15$，有$s[5]$%$2==1$；$cnt$数组中$cnt[1]==2$，因此res=res+2=4+2==6；然后就退出循环了。

(在这个模拟里面中，可以看出把$cnt[0]=1$的原因了；大家可以试试若不把$cnt[0]$赋初值的话，答案是哪样的)

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;//表示n个数据
int k;//表示k倍区间
int a[100010];//存放n个数据
long long sum[100010];//存放前缀和的数组
long long cnt[100010];//存放余数的数组
long long res;//存放结果

int main()
{
    //输入数据
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >>a[i];
        sum[i] = a[i]+sum[i - 1];//计算前缀和
    }

    //循环枚举余数相同
    cnt[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        res += cnt[sum[i] % k];
        cnt[sum[i] % k]++;
    }

    //输出数据
    cout << res << endl;

    return 0;
}