1295B.md (1848B)
1 Source: https://codeforces.com/problemset/problem/1295/B 2 3 B. Infinite Prefixes 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 string $s$ of length $n$ consisting of 0-s and 1-s. You build an infinite string $t$ as a concatenation of an infinite number of strings $s$, or $t = ssss \dots$ For example, if $s =$ 10010, then $t =$ 100101001010010... 22 23 Calculate the number of prefixes of $t$ with balance equal to $x$. The balance of some string $q$ is equal to $cnt_{0, q} - cnt_{1, q}$, where $cnt_{0, q}$ is the number of occurrences of 0 in $q$, and $cnt_{1, q}$ is the number of occurrences of 1 in $q$. The number of such prefixes can be infinite; if it is so, you must say that. 24 25 A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd". 26 27 Input 28 29 The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases. 30 31 Next $2T$ lines contain descriptions of test cases — two lines per test case. The first line contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $-10^9 \le x \le 10^9$) — the length of string $s$ and the desired balance, respectively. 32 33 The second line contains the binary string $s$ ($|s| = n$, $s_i \in \{\text{0}, \text{1}\}$). 34 35 It's guaranteed that the total sum of $n$ doesn't exceed $10^5$. 36 37 Output 38 39 Print $T$ integers — one per test case. For each test case print the number of prefixes or $-1$ if there is an infinite number of such prefixes. 40 41 Example 42 43 Input 44 45 ``` 46 4 47 6 10 48 010010 49 5 3 50 10101 51 1 0 52 0 53 2 0 54 01 55 ``` 56 57 Output 58 59 ``` 60 3 61 0 62 1 63 -1 64 ``` 65 66 Note 67 68 In the first test case, there are 3 good prefixes of $t$: with length $28$, $30$ and $32$.