资源限制
时间限制：2.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
　　不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

思想：两个前缀和模k的值相同的区间，可以产生一个k倍区间。

#include<bits/stdc++.h>
using namespace std;
int main() {
	int pre_sum[100001];
	int cnt[100001] = {0};
	int n, k;
	cin >> n >> k;
	pre_sum[0] = 0;
	int num,res = 0;
	for (int i = 1; i <= n; i++) {
		cin >> num;
		pre_sum[i] = (pre_sum[i - 1] + num)%k;
		res += cnt[pre_sum[i]];
		cnt[pre_sum[i]]++;
	}
	res = res + cnt[0];
	cout << res << endl;
	return 0;
}

资源限制

时间限制：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分过了，当然要是第一次接触这类题，感觉这种做法还是很难想的，害，算法之路还是十分漫长啊~

K倍区间

题目

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

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

输入格式

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

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

输出格式

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

数据范围

1 ≤ N , K ≤ 100000 ,
1 ≤ A~i ~≤ 100000

输入样例：

5 2
1
2
3
4
5c

输出样例：

6

题意
给定一段数列和一个整数K，假若其中的一段数之和是K的倍数，则称这段区间为K倍区间，问这段数列有多少个K倍区间

思路
前缀和
摘抄一位大佬的题解（我好菜）

AC代码

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

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL s[N], cnt[N];

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

    LL res = 0;
    cnt[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++ ;
    }

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

    return 0;
}