零、題目描述

題目鏈接：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)$。主要用于存儲前綴和數組和哈希表。