每日算法打卡：K倍区间

算法
1.1k words

原题链接

1230. K倍区间

题目难度：中等

题目来源：第八届蓝桥杯省赛C++ B组,第八届蓝桥杯省赛Java B/C组

题目描述

给定一个长度为 NNN 的数列，$A_1, A_2, … A_N$，如果其中一段连续的子序列 $A_i, A_{i+1}, … A_j$ 之和是 K 的倍数，我们就称这个区间 $[i, j]$ 是 K 倍区间。

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

输入格式

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

以下 NNN 行每行包含一个整数 $A_i$。

输出格式

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

数据范围

$1 \le N, K \le 100000$,
$1 \le A_i \le 100000$

输入样例：

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

输出样例：

1
6

题目分析

题目意思十分清楚，就是给一个静态数组，问其中有多少个连续子数组的和是K的倍数

这里我们观察数据范围，大概采用的时间复杂度要小于$O(n\log n)$

我们如果用最暴力的做法，枚举所有方案，对于枚举来说最重要的就是如何能够不重不漏的枚举出所有方案

对于这个题而言，就是枚举左端点和右端点，这样就可以枚举所有的方案了，然后再判断左右端点之间的和是否是k的倍数，这里的时间复杂度是$O(n^2)$

这里我们想办法找到优化方法，假设先枚举右端点，再枚举左端点，那么对于每一个右端点，他的目的就是要找到有若干左端点，满足K倍条件

这里我们加入前缀和的思想

K倍条件为$(pre[R]-pre[L])%K == 0$

经过变换其实可以变成$pre[R]%K==pre[L]%K$

那么问题就变成了，有多少个$pre[R]$和$pre[L]$的余数相同

那我们其实就可以开一个数组，用于存储在前缀和数组中除K的每个余数的个数

在遍历前缀和数组的过程中，每一次遇到目标的余数，就在答案上加上之前的个数，因为新的数字和之前的每一个数字都算一组新的满足条件的情况，因此只需要$O(n)$的时间

示例代码

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
28
#include<iostream>
using namespace std;
using ll = long long;

const int N = 1e5+10;
int n,k;
ll pre[N]; // 前缀和数组
ll cnt[N]; // 余数数组

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) // 前缀和
    {
        cin>>pre[i];
        pre[i]+=pre[i-1];
    }
    
    ll ans = 0;
    cnt[0] = 1;
    for(int i=1;i<=n;i++) // 枚举右端点
    {
        ans += cnt[pre[i]%k]; // 找到相同余数的数字，加上之前的数
        cnt[pre[i]%k]++; // 添加新的数据
    }
    cout<<ans<<'\n';
    return 0;
}

对于cnt[0] = 1的理解

对于余数非0的数而言，他的结果一定是从0加到总数减1，对于余数是0本身的数，他自身就可以作为一个结果，因此要初始化为1

这里简单举个例子

例如

k = 2

序列为：1,2,3,4,5

前缀和为：1,3,6,10,15

余数为0的：6,10 一共两个

余数为1的：1,3,15 一共三个

我们来模拟一下这个过程

假设从余数为0的时候开始，没有初始化cnt[0] = 1

走到6，ans += 0

走到10，ans += 1

这里的含义就是，从6到10算一种情况，因此余数为0的情况就只有一种

如果余数为1

走到1，ans += 0

走到3，ans += 1

走到15，ans += 2

这里的含义就是走到1，只有一个数，不算区间，不算一次，走到3，1和3算一次，记录，走到15，1和15算一次，3和15算一次，因此加2

所以如果不初始化的话，结果应该是4

这里我们会发现一个问题，如果余数是0的话，他本身也可以作为一个区间

这时我们回头，初始化cnt[0] = 1

走到6，ans += 1

走到10，ans += 2

这里的含义就是，6本身是一种，加1，10本身是一种，6到10是一种，加2，一共就是3种

再加上余数是1的3种

答案就是6，这就是正确答案了

Comments