A drum track is a list nums of beat labels. For a window (a contiguous, non-empty subarray) nums[l..r], call a label rhythmic if it occurs in the window and its number of occurrences in the window is a multiple of m.
Return the sum, over all n * (n + 1) / 2 windows, of the number of rhythmic labels in that window.
Examples
Input: nums = [1, 2, 1, 3, 1], m = 2
Output: 4
Explanation: only label 1 can occur an even number of times. It occurs exactly twice
in [1,2,1], [1,2,1,3], [2,1,3,1] and [1,3,1].
Input: nums = [5, 5, 5, 5], m = 2
Output: 4
Explanation: the three windows of length 2 and the one window of length 4.
Constraints
0 <= n = len(nums) <= 2 * 10**5-10**9 <= nums[i] <= 10**91 <= m <= 2 * 10**5- Large tests have
n = 2 * 10**5, with anything from a handful to about10**5different labels. Looking at the windows one by one is far too slow, and so is scanning the whole list once per label.
Goals
- Turn a sum over all subarrays into a sum over values
- Count pairs of prefix positions with equal residues of an occurrence count
- Exclude pairs of prefixes that enclose no occurrence at all