3729. Count Distinct Subarrays Divisible by K in Sorted Array

You are given an integer array nums sorted in non-descending order and a positive integer k.

A subarray of nums is good if the sum of its elements is divisible by k.

Return an integer denoting the number of distinct good subarrays of nums.

Subarrays are distinct if their sequences of values are. For example, there are 3 distinct subarrays in [1, 1, 1], namely [1], [1, 1], and [1, 1, 1].

class Solution {
public:
    long long numGoodSubarrays(vector<int>& nums, int k) {
        map<long long, long long> freq{{0,1}};
        map<long long, long long> cnt;
        long long sum = 0, res = 0;
        for(auto& n : nums) {
            cnt[n]++;
            sum = (sum + n) % k;
            res += freq[sum];
            freq[sum]++;
        }
        for(auto& [v,c] : cnt) {
            freq = {{0,0}};
            sum = 0;
            for(int i = 0; i < c; i++) {
                sum = (sum + v) % k;
                res -= freq[sum];
                freq[sum]++;
            }
        }

        return res;
    }
};