1217C.md (1357B)
1 Source: https://codeforces.com/problemset/problem/1217/C 2 3 C. The Number Of Good Substrings 4 5 time limit per test 6 7 4 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 a binary string $s$ (recall that a string is binary if each character is either $0$ or $1$). 22 23 Let $f(t)$ be the decimal representation of integer $t$ written in binary form (possibly with leading zeroes). For example $f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$ and $f(000100) = 4$. 24 25 The substring $s_{l}, s_{l+1}, \dots , s_{r}$ is good if $r - l + 1 = f(s_l \dots s_r)$. 26 27 For example string $s = 1011$ has $5$ good substrings: $s_1 \dots s_1 = 1$, $s_3 \dots s_3 = 1$, $s_4 \dots s_4 = 1$, $s_1 \dots s_2 = 10$ and $s_2 \dots s_4 = 011$. 28 29 Your task is to calculate the number of good substrings of string $s$. 30 31 You have to answer $t$ independent queries. 32 33 Input 34 35 The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of queries. 36 37 The only line of each query contains string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of only digits $0$ and $1$. 38 39 It is guaranteed that $\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$. 40 41 Output 42 43 For each query print one integer — the number of good substrings of string $s$. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 0110 52 0101 53 00001000 54 0001000 55 ``` 56 57 Output 58 59 ``` 60 4 61 3 62 4 63 3 64 ```