As You know, this is the midterm week.
Ali's instructor decided to give the first student who solves this challenge a bonus mark, the challenge goes as follows:
Given an array $a$ of length $n$ count the number of ways to choose a prefix $X$ and a suffix $Y$ such that:
Can you help Ali getting this extra mark?
The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$ --- the number of test cases.
The first line of each test case contains two integers $n, k$ $(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)$ --- the number of elements in the array $a$.
The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n$ $(1 \le a_i \le 10^9)$ the elements of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case print only one integer, the answer to the challenge.
| Input | Output |
|---|---|
1 6 3 1 2 3 1 1 1 Copy
|
7 Copy
|
The idea of the solution is that for every value of $X$ between $1$ (first valid value because we can’t take an empty prefix) and $n-1$ (last valid value because we can’t take an empty suffix) we will count how many values of $Y$ will satisfy the conditions.
First, we will create a suffix sum array, suffix[i] = (suffix[i+1] + arr[i]) % k, so the elements of the array will be in the range [0, k-1] . Then we will create a frequency map, and count the frequency of every element in our suffix array.
When we try a prefix of length $X$, we will decrease the frequency of suffix[x]; because there is no overlapping between $X$ and $Y$ so the suffix that ends on index $X$ can not be counted with a prefix of length $X$, then we find the summation of the first $X$ elements $ mod $ k, let it be $sum$.
If $sum % k = b$, the value that we are searching for in our suffix array is $(k - b) % k$ (when we add both of the sums we will get a sum that is divisible by k).
So we add the number of occurences of $(k-b)%k$ to our answer.
The complexity of the solution is $O(NlogN)$ because we are using a map for finding the frequency.