前言
正文
问题描述
给定一个长度为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]进行组合Cm2（其中m=yushu[i]），故Cm2即为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;
}
京公网安备 11010502036488号