codeforces-scrape

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

1398C.md (1578B)


      1 Source: https://codeforces.com/problemset/problem/1398/C
      2 
      3 C. Good Subarrays
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a_1, a_2, \dots , a_n$ consisting of integers from $0$ to $9$. A subarray $a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r$ is good if the sum of elements of this subarray is equal to the length of this subarray ($\sum\limits_{i=l}^{r} a_i = r - l + 1$).
     22 
     23 For example, if $a = [1, 2, 0]$, then there are $3$ good subarrays: $a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0]$ and $a_{1 \dots 3} = [1, 2, 0]$.
     24 
     25 Calculate the number of good subarrays of the array $a$.
     26 
     27 Input
     28 
     29 The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     30 
     31 The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.
     32 
     33 The second line of each test case contains a string consisting of $n$ decimal digits, where the $i$-th digit is equal to the value of $a_i$.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case print one integer — the number of good subarrays of the array $a$.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 3
     47 3
     48 120
     49 5
     50 11011
     51 6
     52 600005
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 3
     59 6
     60 1
     61 ```
     62 
     63 Note
     64 
     65 The first test case is considered in the statement.
     66 
     67 In the second test case, there are $6$ good subarrays: $a_{1 \dots 1}$, $a_{2 \dots 2}$, $a_{1 \dots 2}$, $a_{4 \dots 4}$, $a_{5 \dots 5}$ and $a_{4 \dots 5}$.
     68 
     69 In the third test case there is only one good subarray: $a_{2 \dots 6}$.