【題目敘述】https://codeforces.com/contest/1295/problem/B
- 逐字掃描輸入字串，並計算目前為止的前綴和 (d)。
- 將出現過的前綴和數字及其出現次數，紀錄於 mp。同時記下最大值 (mx) 及最小值 (mn)。
- 字串掃描完畢，需再次更新 mx、mn，確保數字正確。此時的 d 為整個字串的和 (balance)。
- 當 d = 0，
- 且mn <= x <= mx：有無限多種前綴可以符合要求。
- 否則：無解。
- 當 d != 0，
- 如果 x = 0：empty string 是可能解，ans++。
- 檢查 [mn, mx] 區間所有數 (i)，如果 (x-i) / d >= 0 (正負號相同)，且 (x-i) % d == 0：ans += mp[i]。
#include <iostream>
#include <map>
using namespace std;
int t, n, x, d, mx, mn, b, ans;
map <int, int> mp;
string s;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--){
cin >> n >> x;
d = 0;
mx = 0;
mn = 0;
mp.clear();
cin >> s;
for (int i = 0; i < n; i++){
if (s[i] == '0'){
mn = min(mn, d);
d++;
mp[d]++;
}else{
mx = max(mx, d);
d--;
mp[d]++;
}
}
mn = min(mn, d);
mx = max(mx, d);
if (d == 0){
if (mn <= x && x <= mx) cout << "-1\n";
else cout << "0\n";
continue;
}
ans = 0;
if (x == 0) ans++;
for (int i = mn; i <= mx; i++){
if ((x-i) % d == 0 && (x-i) / d >= 0) ans += mp[i];
}
cout << ans << "\n";
}
}