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 ```