2017年第八届蓝桥杯省赛-J.K倍区间

2022-03-07 · 78次阅读 · 原创 · 数据结构与算法

#数学 #前缀和 #蓝桥杯 #题解

原题链接

题面

给定一个长度为 N 的数列，A₁, A₂, …, A_N，如果其中一段连续的子序列 A_i, A_i+1, …, A_j ( i ≤ j ) 之和是 K 的倍数，我们就称这个区间 [i, j] 是 K 倍区间。

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

输入描述

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

以下 N 行每行包含一个整数 A_i ( $1 \leq A_i \leq 10^5$ )。

输出描述

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

输入样例

输出样例

思路

数论，同余，前缀和

由题，找到子序列 a[i], q[i + 1], ..., a[j] 的和为 k 的倍数，将其转化为前缀和 S，则为找到s[j] - s[i - 1] 为 k 的倍数的区间 [i, j]，对于式子：

$(s[j] - s[i - 1]) \mod k = 0$

等价于：

$s[j] \equiv s[i - 1] \mod k$

则对于下标为 j 的元素，只要统计前面元素的前缀和%k 与 当前前缀和s[j]%k相等的数量，即为以下标 j 结尾的子序列和为 k 的倍数的子序列个数。则只要从前往后遍历一遍数组，每到一个下标，则累加之前的前缀和模 k 的余数相等的个数，同时将每个位置的前缀和对 k 求余后的数值记录起来。

注意，初始化时，应该将 0 出现的次数置位 1。若数列为 2,3，k = 2，则走到下标 i = 1 的时候，当前前缀和模2为0，而前面没有出现过前缀和模 k 等于 0 的情况，就少算了一次，所以需要在初始化时做相关操作。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, k, s[N];
long long ans;

int main() {
    map<int, int> mp;
    mp[0] = 1;
    cin >> n >> k;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        s[i] = (s[i - 1] + x) % k;
        ans += mp[s[i]];
        mp[s[i]]++;
    }
    cout << ans << endl;
    return 0;
}

标题：	2017年第八届蓝桥杯省赛-J.K倍区间
链接：	https://www.fightingok.cn/detail/201
更新：	2022-09-18 22:47:45
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可