问题描述

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

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

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式

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

数据范围

1≤N,K≤100000,

1≤Ai≤100000

输入样例：

5 2
1
2
3
4
5

输出样例：

6

思路

这道题涉及到了区间和的计算，所以可以用前缀和的思想来做。

首先，先对传入的区间求一遍前缀和，然后再去遍历每个区间来判断该区间和是否满足 K 的倍数。

就拿题目样例举例，我们看其中一个区间 [2,4]，可以直接利用前缀和数组计算出该区间的和，然后判断是否为 K 的倍数，可以发现该区间和为 15 - 3 = 12，且 k = 2 故满足 K 的倍数，答案加一。

我们在此基础上优化一下，可以用空间换时间，通过题目可以知道区间 [l , r] 的和是 k 的倍数即 ( s u m [ r ] − s u m [ l − 1 ] ) % k = = 0 (sum[r] - sum[l-1]) \% k == 0(sum[r]−sum[l−1])%k==0，可以推出 s u m [ r ] % k = = s u m [ l − 1 ] % k sum[r] \% k == sum [l-1] \% ksum[r]%k==sum[l−1]%k。

再解释下 a n s + = r e s [ s u m [ i ] ] ans += res[sum[i]]ans+=res[sum[i]]。

首先明确 r e s [ s u m [ i ] ] res[sum[i]]res[sum[i]] 表示的是 s u m [ i ] sum[i]sum[i] 出现过的次数。

举个例子，假设 s u m [ i ] = 3 sum[i] = 3sum[i]=3，在后边的循环中，又出现了一个 s u m [ i ] = 3 sum[i] = 3sum[i]=3，那么此时，这个 “3” 可以和前边出现过的所有的 “3” 分别构成一个 K 倍区间，前边的 “3” 一共出现过 r e s [ s u m [ i ] ] res[sum[i]]res[sum[i]] 次，所以此时又新增了r e s [ s u m [ i ] ] res[sum[i]]res[sum[i]] 个 K 倍区间。

代码

前缀和

#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 100010;
int s[N];
int main() {
  scanf("%d%d", &n, &k);
    //计算前缀和
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
    s[i] += s[i - 1];
  }
    //枚举每个区间，判断其和是否为K的倍数
  int res = 0;
  for (int l = 1; l <= n; l++)
    for (int r = l; r <= n; r++)
      if ((s[r] - s[l - 1]) % k == 0)
        res++;
  cout << res << endl;
  return 0;
}

前缀和（优化）

#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 100010;
typedef long long LL;
int sum[N], a[N];   //一个储存前缀和，一个储存余数
int main() {
  scanf("%d%d", &n, &k);
  LL res = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &sum[i]);
    sum[i] = (sum[i] + sum[i - 1]) % k; //求前缀和的余数
    res += a[sum[i]]; //计算可以匹配两两区间结合的数量
    a[sum[i]]++;
  }
    //这里还要加a[0]是因为之前加的是两两区间结合算一次
    //而余数为0是个特殊值，它可以单独算一个，因此要算上余数为0的区间自身
  cout << res + a[0] << endl; 
  return 0;
}