[蓝桥杯 2017 省 B] k 倍区间

题目描述

给定一个长度为 N的数列，A1,A2,….An，如果其中一段连续的子序列 Ai,Ai+1,… Aj(i<=j)之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入格式

第一行包含两个整数 N和 K(1<=N,K<= 10^5)。

以下 N行每行包含一个整数 Ai(1<=Ai<=10^5)。

输出格式

输出一个整数，代表 K 倍区间的数目。

样例 #1

样例输入 #1

1
2
3
4
5
6
5 2
1  
2  
3  
4  
5

样例输出 #1

1
6

提示

时限 2 秒, 256M。蓝桥杯 2017 年第八届

思路

第一步：可以很容易想一个O（n^3）的暴力做法，枚举一遍区间的右端点，在枚举区间的左端点，在枚举左右端点之间所有的数，加起来判断是不是mod k为0。
第二步:进行第一步优化，利用前缀和数组把所有的前缀和预处理出来，这样就可以解决掉第三重循环，变成O（n^2）的复杂度。处理出前缀和数组s之后，求（l,r）区间的和公式为s[r]-s[l-1]；
第三步:由于数据范围是10^5，平方的复杂度肯定会超时，因此还需要在优化掉一重循环，这样可以使用空间换时间的方法。考虑，其实就是要在所有以r为右端点的区间里找到L使得
（s[r]-s[l-1]）%k==0 即在（0~r-1）区间内找到所有的L使得s[L]和s[r]的余数相同。

注意这个题目的数据范围：前缀和很可能会爆int，答案也可能会爆int，因此要用long long来存储！

代码

正解：前缀和+优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010;
LL s[N],cnt[N];//s是前缀和数组，cnt[i]是记录余数为i的数的个数
int n,k;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];//预处理前缀和
    }
    LL res=0;
    cnt[0]=1;
    for(int i=1;i<=n;i++){
        res+=cnt[s[i]%k];
        cnt[s[i]%k]++;
    }
    printf("%lld\n",res);
    return 0;
}