k倍区间 蓝桥杯真题【前缀和+选排列】（c++）

上文链接：分巧克力-蓝桥杯真题 二分查找（c++实现）

k倍区间

给定一个长度为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

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

思路分析

1. 此题是求连续子序列的和为k的倍数，这样的子序列共有多少个。

2. 我的第一想法是暴力枚举。从i枚举,枚举i-n的和，使和对K求余并记录个数，整个过程时间复杂度O(n³),然而对于最大范围为10⁵的数进行枚举会造成运行超时。

3. 该题可以优化静态数的区间和，而前缀和就是优化静态数（已经知道结果的数）区间和的一种方式，即一个数组A[100]有数1,2,3,4,5…,另一个数组S[100]有数1,3,6,10,15…，数组S中除了索引0之外的数其他数S[ i ] = S[ i-1 ]+A[ i ],这样的数组S就叫做前缀和数组。A数组从 i 到 j 的区间和等于S数组中 j - ( i -1 ),所以从i枚举到j时，采用前缀和可以使得复杂度减少为O(n²),然而这样只能求得10⁴的数，得不到满分。

4. 在前缀和的基础上，对前缀和数组中每个数分别对K取余，取余后的数进行分类，分类后选排列 C$\dbinom{2}{m}$(m2​)(m为分类的数目：比如分类后余数为i的数目为m)求得结果即为子序列个数，比如：前缀和数组S={1,3,5,10,15}对K=2取余后为S={1,1,1,0,1}则数组中数为0有1个，数为1有4个，则子序列有C$\dbinom{2}{1}$(12​) + C$\dbinom{2}{4}$(42​) = 6。

算法展示

#include <iostream>
using namespace std;

int main()
{
	int N,K;
	int Ais[100001];
	cin>>N>>K;
	int S[100001];//前缀和数组 
	int rem[100000];//对K取余数组; 
	
	rem[0]=1;//S[0]=0,所以默认S[0]%2 =0 => rem[0] = 1; 
	for(int i = 1;i<=N;i++)
	{
		cin>>Ais[i];
		S[i] = (S[i-1]+Ais[i])%K;//对S[i]取余。 
		rem[S[i]]++; 
	}
	
	long long ans=0;
	for(int j = 0;j<K;j++)
	{
		ans+=(long long) rem[j]*(rem[j]-1)/2;//选排列运算 
	}
	
	cout<<ans<<endl;
	return 0;
}