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

注意事项

• 本题就是求连续子序列的和为k的倍数，这样的子序列共有多少个，这边需要注意数据规模为10^5，因此直接用暴力枚举一定会超时，
• 该题可以优化静态数的区间和，而前缀和就是优化静态数（已经知道结果的数）区间和的一种方式，即一个数组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]到A[j]（以下均假设i<j）之间的序列和就等于S[j]-s[i]+A[i]。采用前缀和可以使得复杂度减少为O(n2),然而这样只能求得10^4的数，得不到满分
• 继续优化，在前缀和的基础上，对前缀和数组中每个数分别对K取余，取余后的数进行分类，由于是K倍区间，因此余数为0~K-1，而如果S[i]%K==S[j]%K，即二者余数相同，那么说明S[j]-S[i]的值一定为K的倍数，而S[j]-S[i]=A[i+1]+…+A[j]，也就说明存在一个序列满足K倍序列。我们用一个yushu[i]表示前缀和数组S中所有对K取余得到的余数为i的元素的个数。
  因此对yushu[i]进行组合C_m²（其中m=yushu[i]），故C_m²即为K倍区间的数量，对yushu数组中每个元素的组合数进行求和，最后再加上yushu[0]的值则为最终的K倍区间的数量，而为什么要加上yushu[0]的值呢？
  因为yushu[0]的值就是表示前缀和数组S中的元素值刚好能够整除K,假设是S[t]%K==0，也就是说从A[0]到A[t]的序列也是满足K倍区间的，因此yushu[0]的值也是满足K倍区间的序列的数量

参考题解

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
long long a[100010],sum[100010],yushu[100010]; 
int main(){
	long long n,k,count=0;
	scanf("%lld%lld",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		//sum为前缀和数组，sum[i]表示数组a的前i+1项和 
		if(i==0)sum[i]=a[i];
		else sum[i]=sum[i-1]+a[i];
		//桶排序，yushu[i]表示sum[i]对k取余的余数为i的个数 
		yushu[sum[i]%k]++;
	} 
	//进行组合数的计算 
	for(int i=0;i<k;i++){ 
		if(yushu[i]){
			count+=(yushu[i]*(yushu[i]-1)/2);	
		}
	}
	printf("%lld\n",count+yushu[0]);//注意最后需要加上yushu[0]的个数 
	return 0;
}

参考链接
https://juejin.im/post/5e7c29cf6fb9a00950602b5f