题目传送门
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… For example, if s = 10010 s= 10010 s=10010, then t = 100101001010010... t= 100101001010010... t=100101001010010...
Calculate the number of prefixes of t with balance equal to x. The balance of some string q is equal to cnt0,q?cnt1,q, where cnt0,q is the number of occurrences of 0 in q, and cnt1,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.
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 " , " a b " , " a b c " a n d " a b c d " "a", "ab", "abc" and "abcd" "a","ab","abc"and"abcd".
Input
The first line contains the single integer T ( 1 ≤ T ≤ 100 ) T (1≤T≤100) T(1≤T≤100) — the number of test cases.
Next 2T lines contain descriptions of test cases — two lines per test case. The first line contains two integers n n n and x ( 1 ≤ n ≤ 105 , ? 109 ≤ x ≤ 109 ) x (1≤n≤105, ?109≤x≤109) x(1≤n≤105,?109≤x≤109) — the length of string s and the desired balance, respectively.
The second line contains the binary string s ( ∣ s ∣ = n , s i ∈ 0 , 1 ) . s (|s|=n, si∈{0,1}). s(∣s∣=n,si∈0,1).
It’s guaranteed that the total sum of n doesn’t exceed 105.
Output
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.
input
4
6 10
010010
5 3
10101
1 0
0
2 0
01
output
3
0
1
-1
Note
In the first test case, there are 3 good prefixes of t: with length 28, 30 and 32.
题意
-
给定一个长度为n的字符串s，由字符0和1组成
-
你可以让这个字符串s无限延长
-
就令字符串 t = s s s s s s s . . . . . . t=sssssss...... t=sssssss......
-
求字符串t有多少个前缀字符串中， b a l a n c e balance balance 等于 x x x【 b a l a n c e ： 0 的 个 数 ? 1 的 个 数 balance ： 0的个数 - 1的个数 balance：0的个数?1的个数】
-
如果无限解，输出 ? 1 -1 ?1, 注意空串，算作前缀
题解
- 考虑字符串 s s s，设 a a a：某一个前缀 b a l a n c e balance balance ， b b b ：字符串 s s s最后一个字符的 b a l a n c e balance balance，即求，是否存在 x = k ? a + b （ k 属 于 正 整 数 ） x = k * a + b （k 属于 正整数 ） x=k?a+b（k属于正整数）
- 首先考虑无限解：如果每次迭代之后 b a l a n c e = 0 balance = 0 balance=0，即，次数 k k k 不影响 x x x，那么当 s s s 的任意一个前缀 b a l a n c e = x balance = x balance=x 时，有无穷多解。
- 如果 s s s 末尾 b a l a n c e ! = 0 balance !=0 balance!=0 ，则不存在无穷多解。因为对于某一固定的位置，无论迭代次数如何，这一位置的取值单调 ，只可能和x有一个交点。当 （ x ? a ） % b = = 0 （x-a）\% b==0 （x?a）%b==0 时，必定有解，且当前位置只有一个解，ans++。
AC-Code
int tonghao(int a, int b) {
if ((a >= 0 && b > 0) || (a <= 0 && b < 0)) return true;else return false;
}int main()
{
int t;while (scanf("%d", &t) != EOF) {
while (t--) {
int n, x, num = 0;char str[100005];int strn[100005];memset(strn, 0, sizeof(strn));scanf("%d%d", &n, &x);scanf("%s", str);for (int i = 0; i <= n - 1; i++) strn[i + 1] = str[i] == '1' ? strn[i] - 1 : strn[i] + 1;if (strn[n] == 0) {
bool inf = false;for (int i = 0; i <= n; i++) if (strn[i] == x) inf = true;if (!inf) printf("0\n");else printf("-1\n");continue;}else {
for (int i = 1; i <= n; i++) if (tonghao(x - strn[i], strn[n]) && (x - strn[i]) % strn[n] == 0) num++;if (x == 0) num++;}printf("%d\n", num);}}return 0;
}