codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.