codeforces-scrape

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

1996E.md (1332B)


      1 Source: https://codeforces.com/problemset/problem/1996/E
      2 
      3 E. Decode
      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 In a desperate attempt to obtain your waifu favorite character, you have hacked into the source code of the game. After days of struggling, you finally find the binary string that encodes the gacha system of the game. In order to decode it, you must first solve the following problem.
     22 
     23 You are given a binary string $s$ of length $n$. For each pair of integers $(l, r)$ $(1 \leq l \leq r \leq n)$, count the number of pairs $(x, y)$ $(l \leq x \leq y \leq r)$ such that the amount of $\mathtt{0}$ equals the amount of $\mathtt{1}$ in the substring $s_xs_{x+1}...s_y$.
     24 
     25 Output the sum of counts over all possible $(l, r)$ modulo $10^9+7$.
     26 
     27 Input
     28 
     29 The first line contains $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     30 
     31 Each test case contains a binary string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$). It is guaranteed $s$ only contains characters $\mathtt{0}$ and $\mathtt{1}$.
     32 
     33 It is guaranteed the sum of $|s|$ over all test cases does not exceed $2 \cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, output an integer, the answer modulo $10^9+7$.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 0000
     47 
     48 01010101
     49 
     50 1100111001
     51 
     52 11000000111
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 0
     59 130
     60 147
     61 70
     62 ```