B. Infinite Prefixes

题意：给定一个01字符串s，t是无限个01字符串s相连，现在，求这个字符串t中有多少个前缀使得这个前缀的0的个数大于1的个数为x。

分析：对于01字符串的贡献问题，我们可以把01字符串中0替换成1累加到前缀和中，1替换成-1，累加到前缀和中，这样，我们就能得到一个前缀中01字符的相对关系，比如前缀和等于3，说明0的个数比1的个数多3，然后，我们分情况讨论，首先，如果整个字符串s结束了的贡献为0，说明0和1之间的数量是相同的，随着字符串t的增长，如果这个子串中有个位置的前缀和等于x，说明随着字符串s的无限增长，就会有无穷个前缀等于x，如果这个子串中没有一个位置的前缀和等于x，说明随着字符串的增长，不会有字符串的贡献等于x，输出0，然后我们再讨论一个子串的贡献不是0的，我们如何去确定一个前缀和的贡献等于x，如果一个sum[i] + k * sum[n] == x，那么它就是一个符合的位置，那么只要这个k是整数，那么这个前缀和的贡献就是符合的，然后就可以得到(x - sum[i]) % t == 0这个条件，同时，我们还要保证(x - sum[i])和sum[n]同号，因为我们需要x - sum[i] == k * sum[n]，k是一个非负的整数，那么sum[n]和x - sum[i]应该是同号的。同时，还有个小细节，就是空串，空串的贡献应该为0，如果我们的x等于0，那么就增加答案。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100005;
int sum[N];

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		int n, x;
		cin >> n >> x;

		char a;
		for (int i = 1; i <= n; ++i)
		{
			cin >> a;
			if (a == '0')
				sum[i] = sum[i - 1] + 1;
			else
				sum[i] = sum[i - 1] - 1;
		}

		//第一种情况
		if (sum[n] == 0)
		{
			for (int i = 1; i <= n; ++i)
			{
				if (sum[i] == x)
				{
					cout << -1 << endl;
					goto here;
				}
			}

			cout << 0 << endl;
			goto here;
		}
		else
		{
			int res = 0;

			//空串情况
			if (x == 0)
				++res;

			for (int i = 1; i <= n; ++i)
			{
				if ((x - sum[i]) % sum[n] == 0 && (x - sum[i]) / sum[n] >= 0)
					++res;
			}
			cout << res << endl;
		}
		

		here:;
	}


	return 0;
}