给定一个长度为 N N 的数列, A 1 , A 2 , ⋯ A N A 1 ,A 2 ,⋯A N ,如果其中一段连续的子序列 A i , A i + 1 , ⋯ A j ( i ≤ j ) A i ,A i+1 ,⋯A j (i≤j) 之和是 K K 的倍数,我们就称这个区间 [ i , j ] [i,j] 是 K K 倍区间。 你能求出数列中总共有多少个 K K 倍区间吗? 输入格式 第一行包含两个整数 N N 和 K K ( 1 ≤ N , K ≤ 1 0 5 ) (1≤N,K≤10 5 )。 以下 N N 行每行包含一个整数 A i A i ( 1 ≤ A i ≤ 1 0 5 ) (1≤A i ≤10 5 )。 输出格式 输出一个整数,代表 K K 倍区间的数目。 输入 #1 复制代码 5 2 1 2 3 4 5 输出 #1 复制代码 6 提示 时限 2 秒, 256M。蓝桥杯 2017 年第八届给定一个长度为 N N 的数列, A 1 , A 2 , ⋯ A N A 1 ,A 2 ,⋯A N ,如果其中一段连续的子序列 A i , A i + 1 , ⋯ A j ( i ≤ j ) A i ,A i+1 ,⋯A j (i≤j) 之和是 K K 的倍数,我们就称这个区间 [ i , j ] [i,j] 是 K K 倍区间。 你能求出数列中总共有多少个 K K 倍区间吗? 输入格式 第一行包含两个整数 N N 和 K K ( 1 ≤ N , K ≤ 1 0 5 ) (1≤N,K≤10 5 )。 以下 N N 行每行包含一个整数 A i A i ( 1 ≤ A i ≤ 1 0 5 ) (1≤A i ≤10 5 )。 输出格式 输出一个整数,代表 K K 倍区间的数目。 输入 #1 复制代码 5 2 1 2 3 4 5 输出 #1 复制代码 6 提示 时限 2 秒, 256M。蓝桥杯 2017 年第八届 c++代码
时间: 2025-03-12 07:21:07 浏览: 86
<think>好的,我现在需要解决用户的问题,即如何用C++编写程序来计算数列中K倍区间的数量。这个问题来自蓝桥杯竞赛,所以需要考虑时间效率和正确性。首先,我得仔细理解题目要求。题目说,给定一个长度为N的数列,找出所有连续子序列的和是K的倍数的区间数量。用户需要的是C++代码实现。
首先,我想到最直接的暴力解法:遍历所有可能的子序列,计算它们的和,然后判断是否是K的倍数。但这样的话时间复杂度是O(N²),当N很大时(比如1e5),这样的方法肯定会超时。所以必须找到一个更高效的算法。
这时候,我应该考虑前缀和的方法。前缀和数组可以快速计算任意区间的和,即sum[i...j] = prefix[j] - prefix[i-1]。如果这个差值能被K整除,那么就有(prefix[j] - prefix[i-1])% K == 0,也就是prefix[j] % K == prefix[i-1] % K。因此,问题可以转化为统计前缀和模K相等的次数。
接下来,我需要用哈希表或者数组来记录每个余数出现的次数。例如,假设当前计算到第j个元素的前缀和模K的余数是r,那么在之前有多少个前缀和的余数也是r,那么这些位置i-1到j的区间和都是K的倍数。因此,每遇到一个余数r,就将计数器加上之前这个余数出现的次数,然后更新哈希表中的余数次数。
需要注意的是,前缀和数组通常从1开始,而实际编程中数组可能从0开始,需要处理好下标的问题。此外,余数可能是负数的情况,这时候需要转换为正数,比如通过(r % K + K)% K来确保余数在0到K-1之间。
另外,还要考虑前缀和为0的情况。比如,当某个前缀和本身是K的倍数时,这个前缀和单独就可以构成一个K倍区间,所以初始化时哈希表中应该预先存入余数0的次数为1,这样在遇到余数为0的时候可以直接加上这个初始值。
举个例子,假设K=2,数组是[1,2,3,4]。前缀和数组是[0,1,3,6,10],对应的模2余数是[0,1,1,0,0]。当计算到第一个余数0的时候,初始次数是1,此时计数器增加1-1=0?或者需要更仔细分析?
可能我的思路需要再理一遍。假设哈希表初始化为cnt[0] = 1。当计算到第i个前缀和s时,余数r = s % K。此时,前面有多少个余数等于r的,就会产生多少个符合条件的区间。所以每次将cnt[r]的值加到结果中,然后将cnt[r]加1。
例如,初始时cnt[0]=1。假设第一个前缀和余数是r,那么结果加上cnt[r],此时如果r是0的话,结果加1,然后cnt[0]变成2。这可能对应的是从开始到当前位置的区间和满足条件的情况。
现在,我需要验证这个方法的正确性。比如,当数组为[2,3],K=5。前缀和为0,2,5。余数为0,2,0。当处理第一个余数0时,结果加1(因为初始cnt[0]=1),然后cnt[0]变成2。处理到第二个余数0时,结果加2,此时总共有1+2=3?但实际上正确的K倍区间应该是[2,3]的和5,以及前两个元素的和5,以及第三个余数0的情况?
或者可能我在这里理解有误。可能例子中的数组是[2,3],前缀和数组是0,2,5。余数对5取模是0,2,0。那么初始时cnt[0]=1。处理第一个余数0时,结果加1,然后cnt[0]增加到2。处理第二个余数2时,结果加0(因为cnt[2]初始为0),然后将cnt[2]设为1。处理第三个余数0时,结果加2(此时cnt[0]=2),所以总共有1+0+2=3个区间。这三个区间应该是:
区间0-0(前缀和为0,可能不算?或者初始条件的问题),或者具体的区间可能包括:
当余数0出现的时候,比如前缀和5,余数0,此时之前有两个余数0的情况(初始和第一个前缀和),所以对应的是区间[1-2](和为5)和初始到当前位置(整个数组的和5)。可能这里需要仔细考虑。
或者,可能我的例子选择有误,导致计算出现偏差。可能需要重新选择一个例子来验证。
假设数组是[3,1,2,7,4],K=5。正确的结果是多少?
计算各个子数组的和是否是5的倍数:
比如,3 →3(不是),3+1=4→不是,3+1+2=6→不是,3+1+2+7=13→不是,3+1+2+7+4=17→不是。然后1→1,1+2=3,1+2+7=10→是,10是5的倍数。所以这个区间是[2,4]。还有1+2+7+4=14→不是。接着2→2,2+7=9→不是,2+7+4=13→不是。7→7→不是,7+4=11→不是。4→4→不是。此外,子数组可能还有其他情况,比如单独7+4=11→不是。可能我举的例子结果较少。
或者,可能需要更简单的例子。比如数组是[5],K=5。此时结果应为1。根据算法,前缀和为0,5。余数分别是0和0。初始时cnt[0]=1。处理第一个余数0时,结果加1,然后cnt[0]变为2。处理第二个余数0时,结果加2,总共有1+2=3?这显然不正确,说明哪里出错了。
这说明我的算法可能存在错误。这时候必须重新思考。
问题可能出在初始化的处理上。例如,当计算前缀和数组时,前缀和数组的长度是N+1,其中prefix[0]=0,prefix[1]=a[0],依此类推。那么,当处理到prefix[i]的时候,余数是r,那么需要查找前面有多少个prefix[j]的余数等于r,其中j从0到i-1。因此,初始化时,cnt[0] =1,对应的是prefix[0]的余数0。这样,当处理第一个元素prefix[1]时,计算余数r=prefix[1]%K。然后结果加上cnt[r],然后将cnt[r]加1。这样,当数组只有一个元素5的时候,K=5。prefix数组是[0,5]。余数分别是0和0。处理到i=1的时候,余数0,此时cnt[0]是1,所以结果加1。然后cnt[0]变为2。处理到i=2的时候,假设数组长度是1,则循环结束。总共有1个正确的区间。但按照之前的例子,此时得到的结果应该是正确的。
可能刚才我的测试例子中的处理步骤有误。假设数组长度为N=1,元素为5。前缀和数组是0,5。余数0和0。初始化cnt[0]=1。第一次循环处理i=1时,余数r=5%5=0。此时结果加上cnt[0]即1,总结果为1。之后cnt[0]变为2。循环结束。所以结果是正确的,得到1个区间。这说明算法是正确的。
那之前的错误例子中的情况可能是我计算方式的问题。例如,数组是[5],K=5。正确的结果是1个区间,即[0,0]。而算法得到的结果是1,正确。
另一个例子,数组是[2,3],K=5。前缀和是0,2,5。余数是0,2,0。初始化cnt[0]=1。处理i=1时,余数2。此时cnt[2]是0,结果加0。然后将cnt[2]设为1。处理i=2时,余数是0,此时cnt[0]是1,结果加1,总结果为1。然后将cnt[0]设为2。总共有1个区间,即[0,1]的和5。那这个是否正确?
是的,因为子数组[0,1]的和是5,符合条件。所以此时算法得到的结果是1,正确。
这说明算法是正确的。那另一个例子,比如数组是[4,5,0,-2,-3,1],K=5。这个例子可能有多个符合条件的区间。比如,4+5+0=9,不是。5+0=5,是。0是。4+5+0+(-2)+(-3)+1=5,是。可能还有其他情况。但用该算法是否能正确计算?
现在,回到问题,正确的算法思路应该是:
- 计算前缀和数组prefix,其中prefix[0]=0,prefix[i] = a[0]+a[1]+...+a[i-1]。
- 对于每个prefix[i],计算余数r = (prefix[i] % K + K) % K(处理负数情况)。
- 使用哈希表或数组cnt统计每个余数出现的次数。
- 初始化cnt[0] = 1,因为prefix[0]的余数是0,此时还没有元素。
- 遍历i从1到N(即每个prefix[i]):
- 计算余数r。
- 将cnt[r]的值加到结果中,因为这表示前面有cnt[r]个prefix[j](j <i)的余数相同,从而区间[j..i-1]的和是K的倍数。
- 将cnt[r]增加1。
这样,总的结果就是所有符合条件的区间的数量。
现在,我需要用C++来实现这个思路。需要注意数据类型的范围。假设N的范围是1e5,每个数可能是正数或负数,所以前缀和可能很大,但用模运算之后,余数只需要保存0到K-1的值。因此,可以用一个数组或者unordered_map来保存余数的次数。当K可能大到1e9的时候,用unordered_map更合适,否则如果K较小,可以用数组。但题目没有给出K的范围,所以最好用unordered_map。
但蓝桥杯的原题中,K的范围可能较小?需要确认。根据题目描述,可能K的范围可以是任何整数,所以使用哈希表更安全。
此外,前缀和可能会溢出,所以每次计算前缀和的时候要取模。这样可以避免数值过大。例如,prefix[i] = (prefix[i-1] + a[i-1]) % K。但要注意负数的情况,所以正确的处理方式是prefix[i] = (prefix[i-1] + a[i-1] % K + K) % K。或者,更简单的方法是每次累加并取模,同时处理负数的情况。例如:
prefix_mod[i] = (prefix_mod[i-1] + a[i-1]) % K;
但是这样可能得到负数余数,因此需要调整为正数:
r = (prefix_mod[i] % K + K) % K;
或者,在每次计算时确保余数为正。
综上,C++代码的大致步骤如下:
1. 读取N和K。
2. 读取数组a。
3. 初始化prefix_mod为0,cnt哈希表,初始值cnt[0] = 1。
4. 遍历每个元素,计算当前前缀模K的值。
5. 对于每个当前余数r,将结果加上cnt[r],然后cnt[r]++.
这样,就可以得到所有满足条件的区间数量。
现在,编写代码的步骤:
代码示例:
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
long long sum = 0; // 当前前缀模K的值
unordered_map<int, int> cnt;
cnt[0] = 1; // 初始余数0出现一次
long long result = 0;
for (int i = 0; i < N; ++i) {
int num;
cin >> num;
sum += num;
int r = (sum % K + K) % K; // 确保余数为非负数
result += cnt[r];
cnt[r]++;
}
cout << result << endl;
return 0;
}
但是,这可能有问题。因为sum的值可能会非常大,导致sum % K的溢出。因为当sum超过long long的范围时,取模的结果可能不正确。为了避免这种情况,应该在每次累加时都取模,保持sum的值在合理范围内。例如:
sum = (sum + num % K + K) % K;
这样,sum始终是模K后的余数,这样就不会溢出。因为每次加上num之后,立即取模。
修改后的代码:
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
long long sum_mod = 0; // 当前前缀模K的值
unordered_map<int, int> cnt;
cnt[0] = 1;
long long result = 0;
for (int i = 0; i < N; ++i) {
int num;
cin >> num;
// 计算当前数的模K的正余数
int mod = num % K;
if (mod < 0) mod += K;
sum_mod = (sum_mod + mod) % K;
result += cnt[sum_mod];
cnt[sum_mod]++;
}
cout << result << endl;
return 0;
}
这可能更正确,因为每次累加都处理了当前数的余数,并保持sum_mod的正确性。例如,对于num为负数的情况,比如num=-3,K=5,mod=(-3%5)=2?或者需要计算为2?因为-3 mod5=2。所以代码中的处理是正确的:如果mod是负数,就加上K。这样,sum_mod始终是正确的余数。
例如,假设K=5,num=-3。则mod = (-3 %5) →在C++中,-3%5的结果是-3。此时mod <0,所以mod +=5 →2。这样sum_mod加上2,并取模5。这是正确的。
这样,sum_mod的值始终是当前前缀和的余数。然后,每次result加上cnt[sum_mod],并且cnt[sum_mod]自增。这样,当多个前缀和的余数相同时,就能正确统计。
现在,验证一下之前的例子:
例1:数组是[5],K=5。sum_mod初始为0。第一个循环:
num=5 →mod=0 →sum_mod=(0+0)%5=0。result += cnt[0] →1。然后cnt[0]变为2。最终结果1,正确。
例2:数组是[2,3], K=5。sum_mod初始0。第一次循环,num=2 →mod=2 →sum_mod=0+2=2。result += cnt[2] →0。cnt[2]=1。第二次循环,num=3 →mod=3 →sum_mod=(2+3)=5 mod5=0。result += cnt[0] →1。总结果为1。正确,因为只有子数组[0,1]的和是5,符合条件。
另一个例子,数组是[4,5,0,-2,-3,1],K=5:
每个元素的mod计算:
4 mod5=4 →sum_mod=4 →余数4。此时cnt[4]初始0 →result +=0。cnt[4]=1.
第二个元素5 mod5=0 →sum_mod=4+0=4 mod5=4 →余数4。result +=1(cnt[4]是1)→总result=1。cnt[4]=2.
第三个元素0 →sum_mod=4+0=4 mod5=4 →result +=2 →总result=3. cnt[4]=3.
第四个元素-2 mod5=3 →sum_mod=(4+3) mod5=7 mod5=2 →result += cnt[2] →0. 总result=3. cnt[2]设为1.
第五个元素-3 mod5=2 →sum_mod=2+2=4 mod5=4 →result +=3 →总result=6. cnt[4]=4.
第六个元素1 →mod=1 →sum_mod=4+1=5 mod5=0 →result +=cnt[0](初始是1)→总result=7. cnt[0]变为2.
所以总结果是7。但是正确的区间数量是多少?
实际可能的区间包括:
[1,1] →5 →符合条件。
[2,2] →0 →符合条件。
[2,3] →0+(-2)= -2 →mod5=3 →不符合。
[3,4] →-2 +(-3) =-5 →mod5=0 →符合条件.
[0,5] →4+5+0-2-3+1=5 →mod5=0 →符合条件.
其他符合条件的可能还有:
比如,区间[0,1,2,3,4,5]总和是5,符合条件。
另外,前缀和数组的余数变化:
初始余数0 →出现一次。
处理完第一个元素后余数4 →对应区间无,因为余数4出现1次。
处理完第二个元素(5)余数还是4 →此时余数4出现两次。所以当处理第三个元素0的时候,余数还是4 →此时已经有两次,所以每次处理的时候,结果加之前出现的次数。这样,当第三次余数4出现时,此时result +=之前的两次,总共有2次。这可能对应多个区间。
例如,余数4在前三个元素后的次数是3次。所以每次处理这三个余数4的情况时,会累加1、2次。
可能具体的区间需要详细分析,但根据算法,总结果是正确的。
这说明算法是正确的。所以,代码中的处理是正确的。
综上,最终的C++代码应该如上述所示,其中每次处理num时,计算其模K的正余数,并维护sum_mod,然后用哈希表统计余数出现次数。</think>要解决求数列中K倍区间的数量问题,可以通过前缀和结合哈希表的方法实现,时间复杂度为$O(N)$。以下是具体步骤和C++代码实现:
### 方法思路
1. **前缀和模运算**:计算前缀和的模$K$值,若两个前缀和的模相等,则它们之间的区间和为$K$的倍数。
2. **哈希表统计**:用哈希表记录每个余数出现的次数。若当前余数已出现过$n$次,则新增$n$个符合条件的区间。
3. **负数处理**:通过$(x \% K + K) \% K$确保余数为非负数。
### 代码实现
```cpp
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
unordered_map<int, int> cnt; // 记录余数出现次数
cnt[0] = 1; // 初始余数0出现一次
long long sum_mod = 0, result = 0; // sum_mod为当前前缀和的模K值
for (int i = 0; i < N; ++i) {
int num;
cin >> num;
// 计算当前数的模K正余数
int mod = num % K;
if (mod < 0) mod += K;
sum_mod = (sum_mod + mod) % K; // 更新前缀和的模值
// 累加当前余数已有的出现次数
result += cnt[sum_mod];
// 更新余数出现次数
cnt[sum_mod]++;
}
cout << result << endl;
return 0;
}
```
### 代码说明
1. **输入处理**:读取数列长度$N$和模数$K$。
2. **哈希表初始化**:预先存入余数0的计数为1,表示前缀和为0的情况。
3. **遍历数列**:对每个数计算其对$K$的正余数,累加到前缀和的模值中。
4. **统计结果**:若当前余数$r$已出现过$c$次,则新增$c$个K倍区间,并更新哈希表。
该方法通过线性时间复杂度的计算,高效解决了大规模数据下的K倍区间统计问题[^1]。
阅读全文
相关推荐
















