资源限制
时间限制：1.0s 内存限制：256.0MB
给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？
输入格式
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出格式
-----
输出一个整数，代表K倍区间的数目。
例如，
输入格式
5 2
1
2
3
4
5
程序应该输出：
6
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
当时看到这题时的第一反应是用枚举，将这一串数的每一个区间都遍历一遍，于是有了如下的代码
#include <bits/stdc++.h>using namespace std;long long a[100000];int main(){int n,k;int sum=0,cnt=0;cin>>n>>k;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n;i++){sum=0;for(int j=i;j<n;j++){sum+=a[j];if(sum%k==0){cnt++;}}}cout<<cnt;return 0;}提交后直接超时，过了两个测试点(后面的测试点全部超时)，只有28分。
于是参考了其它博客，发现了一种更好的方法，使用前缀和取模。
我们假设n=5；k=2；
输入的5个数为1,2,3,4,5的话
程序输出6 这6种情况分别是123 1234 2345 345 2 4;
若我们将前i项和的模存到一个数组mod[i]中,mod[1]表示前一项的和的模，mod[2]表示前两项的和的模，以此类推，再将mod[i]相同的个数用一个数组add[mod[i]]存起来，只需要计算C 2 add[i]（高中数学的排列组合，2在上面，add[i]在下面）再加上add[0]的所有结果，便可求得正确答案，极大简化了运算时间。
还是上面那个例子：1 2 3 4 5 假如是输入这5个数
可得mod[1]=1(1%2=1) mod[2]=1((1+2)%2=1) mod[3]=0 mod[4]=0 mod[5]=1
mod=1的个数有3个，mod=0的个数有2个，所以add[0]=2，add[1]=3;
我们先看mod=0的时候，所对应的数是3，4，在（3,4]区间中（注意是左开右闭），4%2=0满足条件，
mod=1的时候，所对应的数是1，2，5，在（1,2]区间中，2%2=0满足条件，（1,5]区间中，2345满足条件(2+3+4+5)%2=0,在(2,5]区间中，345满足条件。
所以可以得出结论，从每一种前缀和(所选两个数的中间的数的和)的情况中任意选择两个数组成的区间都满足是k倍区间，其计算方法其实就是排列组合，上面的例子即可表示为C2 2加上C2 3结果为1+3=4，但实际结果有6种，是由于区间是左开右闭的，加上add[0]的所有结果也就是2和4两种，相当于区间左闭右闭，这两个数本身构成一个k倍区间，4+2=6，刚好是正确答案。
于是可得如下代码：
#include <bits/stdc++.h>using namespace std;long long mod[100010]={0},add[100010]={0};int main(){int n,k,a;long long cnt=0;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a;mod[i]=(mod[i-1]+a)%k;add[mod[i]]++;}for(int i=0;i<n;i++){cnt+=add[i]*(add[i]-1)/2;//排列组合}cout<<cnt+add[0];return 0;}提交后也是直接100分过了，当然要是第一次接触这类题，感觉这种做法还是很难想的，害，算法之路还是十分漫长啊~