← 返回题目列表

Codeforces · 1295/B

B. 无限前缀

中文机器翻译题面 查看原题

给定字符串 $$$s$$$,长度为 $$$n$$$,由 0 和 1 组成。您构建一个无限字符串 $$$t$$$ 作为无限数量字符串 $$$s$$$ 的串联,或 $$$t = ssss \dots$$$ 例如,如果 $$$s =$$$ 10010,则 $$$t =$$$ 100101001010010...

计算余额等于$$$x$$$的$$$t$$$的前缀数量。某个字符串 $$$q$$$ 的余额等于 $$$cnt_{0, q} - cnt_{1, q}$$$,其中 $$$cnt_{0, q}$$$ 是 $$$q$$$ 中 0 出现的次数,$$$cnt_{1, q}$$$ 是 $$$q$$$ 中 1 出现的次数。此类前缀的数量可以是无限的;如果是这样,你就必须这么说。

前缀是由给定字符串的几个首字母组成的字符串,没有任何重新排序。空前缀也是有效前缀。例如,字符串“abcd”有 5 个前缀:空字符串、“a”、“ab”、“abc”和“abcd”。

输入

第一行包含单个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 测试用例的数量。

接下来的 $$$2T$$$ 行包含测试用例的描述 - 每个测试用例两行。第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$-10^9 \le x \le 10^9$$$) — 分别是字符串 $$$s$$$ 的长度和所需的余额。

第二行包含二进制字符串 $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{\text{0}, \text{1}\}$$$)。

保证$$$n$$$的总和不超过$$$10^5$$$。

输出

打印 $$$T$$$ 整数 — 每个测试用例一个。对于每个测试用例,打印前缀的数量,如果存在无限数量的此类前缀,则打印 $$$-1$$$ 。

示例

输入 #1

4
6 10
010010
5 3
10101
1 0
0
2 0
01

输出 #1

3
0
1
-1

注意

在第一个测试用例中,$$$t$$$ 有 3 个好的前缀:长度为 $$$28$$$、$$$30$$$ 和 $$$32$$$。