《哈希表》K倍区间（解题报告）

零、题目描述

题目链接：K倍区间

一、算法概述

  计算子数组和能被k整除的子数组数量的算法。通过前缀和与哈希表的结合，高效地统计满足条件的子数组。
  需要注意的是，题目要求求的是 k 的非负整数倍，而非整数倍，所以哈希表的值光存储次数是不够的，需要维护一个列表，在枚举到第 i 个元素的时候，在哈希表 hashset[ sum[i]%k ] 的所有列表元素中，统计小于等于 sum[i] 的元素个数进行累加，因为只有小于等于 sum[i] 的值才能保证是 非负整数 倍。

二、算法思路

1. 前缀和数组：计算数组的前缀和数组sum，其中sum[i]表示前i个元素的和。
2. 哈希表与多重集合：使用哈希表hashset，键为前缀和模k的余数，值为对应的前缀和的多重集合。
3. 余数处理：对于每个前缀和sum[i]，计算其模k的余数s，并处理可能的负数余数情况。
4. 查询与统计：在哈希表中查找余数为s的前缀和集合，并统计其中小于当前前缀和的元素数量，累加到结果中。
5. 更新哈希表：将当前前缀和插入到对应的余数集合中。

三、代码实现

#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;
long long sum[100001];

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        sum[i] = sum[i-1] + x;
    }
    long long ans = 0;
    unordered_map<int, multiset<long long> > hashset;
    hashset[0].insert(0);
    
    for(int i = 1; i <= n; ++i) {
        int s = sum[i] % k;
        s = (s + k) % k;
        int cnt = distance(
            hashset[s].begin(),
            hashset[s].upper_bound(sum[i])
        );
        ans += cnt;
        hashset[s].insert(sum[i]);
    }
    cout << ans << endl;

    return 0;
}

四、算法解释

1. 输入处理：读取数组长度n和除数k，然后读取数组元素并计算前缀和数组。
2. 初始化：初始化结果变量ans为0，并在哈希表中插入初始值(0, 0)，处理空数组的情况。
3. 遍历前缀和数组：
   • 计算当前前缀和模k的余数s，并处理负数余数。
   • 在哈希表中查找余数为s的前缀和集合，统计其中小于当前前缀和的元素数量（注意注意！这题的核心在这里，要求的是非负整数倍，所以必须要找集合中 小于 当前 sum[i] 的元素值，利用二分去找hashset[s].upper_bound(sum[i])）。
   • 将当前前缀和插入到对应的余数集合中。
4. 输出结果：输出满足条件的子数组数量。

五、复杂度分析

1. 时间复杂度：随机数据是 $O(nlogn)$ 的，如果可以构造数据，会达到 $O(n^2)$，本题数据较弱。
2. 空间复杂度：$O(n)$。主要用于存储前缀和数组和哈希表。