2276C.md (2146B)
1 Source: https://codeforces.com/problemset/problem/2276/C 2 3 C. Subarrays 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Monocarp has an array $a$ consisting of $n$ positive integers. He also has a favorite integer $k$ ($k \lt n$). 22 23 A sequence of consecutive elements of the array with indices from $l$ to $r$ ($1 \le l \le r \le n$) is called a subarray. Monocarp calls a subarray $k$-balanced if the following conditions hold: 24 25 * the sum of all elements in the subarray from $l$ to $r$ inclusive is divisible by $k$; 26 * the length of this subarray is strictly greater than $k$ (that is, $r - l + 1 \gt k$). 27 28 Help Monocarp determine the total number of $k$-balanced subarrays in the array $a$. 29 30 Input 31 32 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 33 34 The descriptions of the test cases follow. 35 36 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \lt n \le 2 \cdot 10^5$) — the number of elements in the array $a$ and the number $k$. 37 38 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$. 39 40 Additional constraints on the input: 41 42 * the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, print one integer — the number of $k$-balanced subarrays in the array $a$. 47 48 Example 49 50 Input 51 52 ``` 53 3 54 55 5 2 56 57 2 1 3 1 4 58 59 9 3 60 61 1 1 1 1 1 1 1 1 1 62 63 4 3 64 65 2 8 5 7 66 ``` 67 68 Output 69 70 ``` 71 2 72 73 5 74 75 0 76 ``` 77 78 Note 79 80 In the first test case of the example, the suitable subarrays are: 81 82 1. $[2, 1, 3]$ (the sum of all elements $2 + 1 + 3 = 6$ is divisible by $2$); 83 2. $[3, 1, 4]$ (the sum of all elements $3 + 1 + 4 = 8$ is divisible by $2$). 84 85 In the second test case, all elements are equal to $1$, and $k = 3$. The suitable subarrays have lengths $6$ and $9$: there are four subarrays of length $6$ and one subarray of length $9$, so the answer is $5$. 86 87 In the third test case, the only subarray of length strictly greater than $3$ is the entire array. Its sum is $22$, which is not divisible by $3$, so the answer is $0$.