Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Use signs instead of bits: 1 becomes , 0 becomes . A length- window is valid exactly when the sign of its sum equals its first character.
Neighboring window sums satisfy
If , the sign of the next window cannot flip. The only “interesting” window sum is or .
Fix the sign of the first window. If it is positive, then until the first window with sum exactly , all left endpoints are forced to be 1. Negative is the same story with 0.
If the first weak window is at position , then the block after it has length and is perfectly balanced. After that, the string repeats with period .
So every valid string is either: a constant forced prefix plus a suffix with strict majority of that bit, or a constant forced prefix plus a balanced periodic suffix. Count those periodic suffixes by sweeping and maintaining constraints for each residue modulo .
Let and . Since is odd, is even.
Turn the string into signs:
1 becomes ;0 becomes .For the window starting at , define
The window is valid iff its first character is the majority character, which means:
So the sign of must equal .
The key transition
Consecutive window sums satisfy
If , then , so
which is either or . It stays positive.
Similarly, if , the next sum stays negative.
So the sign can only change when the current window sum is exactly or . That is the whole damn lock.
Classifying strings
Handle the case where the first window has positive sum. The negative case is identical after swapping 0 and 1.
Let , the number of windows.
There are two cases.
Case 1: every window is strongly positive
If all window sums are greater than , then every left endpoint must be 1. So positions through are forced to be 1.
The last positions are not left endpoints. The final window has one forced 1 plus these positions. For the final window sum to be greater than , the last positions must contain more than ones.
So this case is easy: check the forced prefix against the pattern, then count suffix assignments with more than copies of the chosen bit using binomial coefficients.
Case 2: first weak positive window
Suppose is the first position with
Before , the window sums are strongly positive, so
Since and ,
For the next window to be valid, we need
Repeating this gives
So after position , the string is periodic with period .
Also, means the following positions have total sign sum . In bit language, one period block contains exactly zeros and ones.
There is one small gotcha: if , then must really be the first weak window. This forces the last character of the balanced period block to be 0 in the positive case. If it were 1, the previous window would already have sum $1, causing double counting. For the negative case, the forced last character is 1`.
Counting weak cases
For each majority bit in {0,1}, sweep the first weak position .
For this :
The periodic suffix groups positions by residue modulo . For each residue, fixed pattern characters inside the suffix may force that residue to 0, force it to 1, leave it free, or create a contradiction.
If there are no contradictions, and among the period positions:
then the number of balanced period blocks is
The extra forced last character for is handled by adjusting one residue: if that residue is free, it stops being free; if it is already forced wrong, this contributes .
Efficient sweep
Initialize the residue constraints for suffix positions , which corresponds to .
When moving from to :
So each fixed pattern character is inserted/removed from the maintained residue counts only once. We maintain four totals: free residues, forced-0 residues, forced-1 residues, and conflicting residues.
Binomial coefficients are precomputed with factorials and inverse factorials modulo .
Total complexity is per test case, which is because . Memory is .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 998244353;
int modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return (int)r;
}
int main() {
setIO();
const int MAXN = 100000;
vector<int> fact(MAXN + 1), invfact(MAXN + 1);
fact[0] = 1;
for (int i = 1; i <= MAXN; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
invfact[MAXN] = modpow(fact[MAXN], MOD - 2);
for (int i = MAXN; i >= 1; i--) invfact[i - 1] = (ll)invfact[i] * i % MOD;
auto C = [&](int nn, int rr) -> int {
if (rr < 0 || rr > nn) return 0;
return (ll)fact[nn] * invfact[rr] % MOD * invfact[nn - rr] % MOD;
};
int T;
cin >> T;
while (T--) {
int n, k;
string s;
cin >> n >> k >> s;
int L = k - 1;
int h = L / 2;
int m = n - L;
int ans = 0;
auto addAns = [&](int x) {
ans += x;
if (ans >= MOD) ans -= MOD;
};
for (int c = 0; c <= 1; c++) {
bool okPrefix = true;
for (int i = 0; i < m; i++) {
if (s[i] != '?' && s[i] - '0' != c) okPrefix = false;
}
if (okPrefix) {
int forcedC = 0, freeCnt = 0;
for (int i = m; i < n; i++) {
if (s[i] == '?') freeCnt++;
else if (s[i] - '0' == c) forcedC++;
}
for (int need = h + 1; need <= L; need++) {
addAns(C(freeCnt, need - forcedC));
}
}
vector<array<int, 2>> cnt(L);
for (int i = 1; i < n; i++) {
if (s[i] != '?') cnt[i % L][s[i] - '0']++;
}
auto getState = [&](int r) -> int {
bool has0 = cnt[r][0] > 0;
bool has1 = cnt[r][1] > 0;
if (!has0 && !has1) return 0;
if (has0 && !has1) return 1;
if (!has0 && has1) return 2;
return 3;
};
vector<int> state(L);
int freeCnt = 0, forced0 = 0, forced1 = 0, conflict = 0;
auto addState = [&](int st) {
if (st == 0) freeCnt++;
else if (st == 1) forced0++;
else if (st == 2) forced1++;
else conflict++;
};
auto removeState = [&](int st) {
if (st == 0) freeCnt--;
else if (st == 1) forced0--;
else if (st == 2) forced1--;
else conflict--;
};
for (int r = 0; r < L; r++) {
state[r] = getState(r);
addState(state[r]);
}
int badPrefix = 0;
for (int a = 1; a <= m; a++) {
if (s[a - 1] != '?' && s[a - 1] - '0' != c) badPrefix++;
if (badPrefix == 0 && conflict == 0) {
int forcedCNow = c ? forced1 : forced0;
if (a == 1) {
addAns(C(freeCnt, h - forcedCNow));
} else {
int r = (a - 1) % L;
int st = state[r];
if (st == 0) {
addAns(C(freeCnt - 1, h - forcedCNow));
} else if ((c == 0 && st == 2) || (c == 1 && st == 1)) {
addAns(C(freeCnt, h - forcedCNow));
}
}
}
if (a < m && s[a] != '?') {
int r = a % L;
int b = s[a] - '0';
removeState(state[r]);
cnt[r][b]--;
state[r] = getState(r);
addState(state[r]);
}
}
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 998244353;
int modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return (int)r;
}
int main() {
setIO();
const int MAXN = 100000;
vector<int> fact(MAXN + 1), invfact(MAXN + 1);
fact[0] = 1;
for (int i = 1; i <= MAXN; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
invfact[MAXN] = modpow(fact[MAXN], MOD - 2);
for (int i = MAXN; i >= 1; i--) invfact[i - 1] = (ll)invfact[i] * i % MOD;
auto C = [&](int nn, int rr) -> int {
if (rr < 0 || rr > nn) return 0;
return (ll)fact[nn] * invfact[rr] % MOD * invfact[nn - rr] % MOD;
};
int T;
cin >> T;
while (T--) {
int n, k;
string s;
cin >> n >> k >> s;
int L = k - 1;
int h = L / 2;
int m = n - L;
int ans = 0;
auto addAns = [&](int x) {
ans += x;
if (ans >= MOD) ans -= MOD;
};
for (int c = 0; c <= 1; c++) {
bool okPrefix = true;
for (int i = 0; i < m; i++) {
if (s[i] != '?' && s[i] - '0' != c) okPrefix = false;
}
if (okPrefix) {
int forcedC = 0, freeCnt = 0;
for (int i = m; i < n; i++) {
if (s[i] == '?') freeCnt++;
else if (s[i] - '0' == c) forcedC++;
}
for (int need = h + 1; need <= L; need++) {
addAns(C(freeCnt, need - forcedC));
}
}
vector<array<int, 2>> cnt(L);
for (int i = 1; i < n; i++) {
if (s[i] != '?') cnt[i % L][s[i] - '0']++;
}
auto getState = [&](int r) -> int {
bool has0 = cnt[r][0] > 0;
bool has1 = cnt[r][1] > 0;
if (!has0 && !has1) return 0;
if (has0 && !has1) return 1;
if (!has0 && has1) return 2;
return 3;
};
vector<int> state(L);
int freeCnt = 0, forced0 = 0, forced1 = 0, conflict = 0;
auto addState = [&](int st) {
if (st == 0) freeCnt++;
else if (st == 1) forced0++;
else if (st == 2) forced1++;
else conflict++;
};
auto removeState = [&](int st) {
if (st == 0) freeCnt--;
else if (st == 1) forced0--;
else if (st == 2) forced1--;
else conflict--;
};
for (int r = 0; r < L; r++) {
state[r] = getState(r);
addState(state[r]);
}
int badPrefix = 0;
for (int a = 1; a <= m; a++) {
if (s[a - 1] != '?' && s[a - 1] - '0' != c) badPrefix++;
if (badPrefix == 0 && conflict == 0) {
int forcedCNow = c ? forced1 : forced0;
if (a == 1) {
addAns(C(freeCnt, h - forcedCNow));
} else {
int r = (a - 1) % L;
int st = state[r];
if (st == 0) {
addAns(C(freeCnt - 1, h - forcedCNow));
} else if ((c == 0 && st == 2) || (c == 1 && st == 1)) {
addAns(C(freeCnt, h - forcedCNow));
}
}
}
if (a < m && s[a] != '?') {
int r = a % L;
int b = s[a] - '0';
removeState(state[r]);
cnt[r][b]--;
state[r] = getState(r);
addState(state[r]);
}
}
}
cout << ans << '\n';
}
}