k倍区间 前缀和【蓝桥杯2017 C/C++ B组】

标题: k倍区间文章地址https://www.yii666.com/article/754240.html网址:yii666.com

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

先求出每一位的前缀和并取余   那么任意区间[l,r]的和就可以通过sum[r]-sum[l-1]来得到

要求区间和为k的倍数,即(sum[r]%k - sum[l-1])%k==0

移项 sum[r] % k == sum[l-1] % k网址:yii666.com<

那么每两个对k取余得到值相同的sum 就可以组成一个k倍区间

所以我们要统计下余数为0--k-1的前缀和个数

取余为0的前缀和 说明[0,i]区间就已经存在一个k倍区间了   当然他还能跟另一个前缀和取余为0的[0,j]区间 组合成为[i,j]的k倍区间文章来源地址:https://www.yii666.com/article/754240.html

所以刚开始我们应该先把取余为0的个数加上文章来源地址https://www.yii666.com/article/754240.html

然后对于所有取余相同的  两两配对能组成一个k倍区间,那么假设有x个取余相同的前缀和 那么他可以组成 ((x-1)*x)/2 个k倍区间     例如有 4个数 两两组合 3+2+1 = 3*(3-1)=6   

其实是等差数列求和公式   n*(n+1)/2    不过这里的n = x-1; 

#include<bits/stdc++.h>
using namespace std;
//int 只有85分
long long a[],sum[],num[];
int main()
{
int n,k ;
cin >> n >> k;
for(int i = ; i < n; i++){
cin >> a[i];
}
sum[] = a[]%k;
for(int i = ; i < n; i++){
sum[i] = (sum[i-]+a[i])%k; //求每个前缀和并趋于
}
memset(num,,sizeof num);
for(int i = ; i < n; i++){
num[sum[i]] ++; // 统计余数为 0 -- k-1的个数
}
long long ans = num[]; //能取余为0 自己本身就存在一个k倍区间了
for(int i = ; i < k; i++){
ans += (num[i]*(num[i]-))/ ; //两两配对 等差数列 n*(n+1)/2 这里n=num[i]-1
}
cout << ans << endl;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png