题目描述

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

样例

6 2
1
2
3
4
5
5

输出

9

题目分析

对于暴力枚举时间复杂度是O(n^2)的，即区间长度从 1 枚举到 n，计算每个区间是否满足 k 倍区间，但这样的暴力枚举肯定会超时，因此我们需要进行优化。
我们知道对于一个区间是否满足 k 倍区间，我们一般是对于一个位置 i，然后判断前面有多少个子区间满足 sum[i] - sum[j] % k == 0，这时候我们可以转换为 sum[i] 与 sum[j] 对 k 取余是否相等，比如下面的例子 k = 2

下标   1 2 3 4  5  6 
元素   1 2 3 4  5  5
前缀和 1 3 6 10 15 20
余数   1 1 0 0  1  0

对于 i = 5, j = 3, sum[i] = 15, sum[j - 1] = 3(这里减一是因为是前缀和，而这一段区间其实是 j-1 到 i)其余数均为 1 那么区间 3 - 5(3 4 5) 必定是一个 k 倍区间，同理 j = 2，区间 2 - 5(2 3 4 5) 也是一个 k 倍区间，其他的是类似的。要计算 i 前面有多少个余数相同的前缀和，我们需要额外利用一个数组来存储。AC代码里面有对cnt数组稍微详细的注释。

算法

枚举代码

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 1e5 + 10;

int a[N], sum[N];
int n, k;

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    LL cnt = 0;
    for(int i = 1; i <= n - 1; i ++ ) {
        for(int j = 1; j + i - 1 <= n; j ++ ) {
//          cout<<sum[j + i - 1] <<" "<< sum[j - 1]<<endl;
            if((sum[j + i - 1] - sum[j - 1]) % k == 0)cnt ++ ;
        }
//      cout<<endl;
    }
    if(sum[n] % k == 0)cnt++;
    cout<<cnt;
    return 0;
}

AC 代码

#include<iostream>
#include<algorithm>

#define endl '\n';

using namespace std;
typedef long long LL;

const int N = 1e5 + 10;

int a[N], sum[N] ,cnt[N];
int n, k;

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        sum[i] = sum[i] % k;
    }
//  for(int i = 0; i <= n; i ++ ) {
//      cout << cnt[i] << " ";
//  }
//  cout << endl;
    LL res = 0;
    for(int i = 1; i <= n; i ++ ) {
        res = res + cnt[sum[i]];
        cnt[sum[i]] = cnt[sum[i]] + 1;
        // cnt 是用来记录 i 以前与 sum[i] 余数相同的前缀和的个数, 但是不包括前缀和本身就是 k 的倍数的区间, 所以我们还要加上这部分 
        // 下标   1 2 3 4  5  6 
        // 元素   1 2 3 4  5  5
        // 前缀和 1 3 6 10 15 20
        // 余数   1 1 0 0  1  0
        // 对于下标 6, 前缀和余数为 0, 在其前面余数为 0 的有下标 3, 4, 那么区间 4 - 6(4, 5, 5) 和区间 5 - 6(5, 5) 就是 k 的倍数 
        // 但是我们这样计算的仅仅是某一段区间是否为 k 倍区间, 并没有计算从 1 - i 是否满足, 所以要补上这一部分
        // 补上的方法有多种, 可以是让 i 从 0 开始, 也可以是加上下面这个判断, 或者令 cnt[0] = 1 
        if(!sum[i])res++;
    }
    cout<<res;
    return 0;
}