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.
Think of the final string as choosing some positions to keep. Everything not kept is split into gaps, and every gap must be deletable, i.e. have an even number of 1s after filling ?.
A substring can be made deletable iff it contains at least one ?, or it has an even number of fixed 1s. So precompute
Let an “endpoint” mean the last kept position, with before the string. From , you may stop if , or keep some as bit if and can be .
The nasty part is duplicate strings from different embeddings. If two endpoints are possible after the same produced prefix, and , then endpoint is useless: from , delete everything through , then mimic 's future.
After removing useless endpoints, there are never more than two endpoints. If all survived, then and are both false, so both substrings have no ? and odd fixed 1 parity. Their union has even parity, so dominates . Contradiction. Now run a deterministic DP over states of size or .
After all ? are filled, deleting several substrings is equivalent to choosing the positions that survive. The deleted characters form independent gaps:
Each such gap must have an even number of 1s. For an incomplete substring , this is possible exactly when
If there is a ?, set it to fix the parity. If there is no ?, the parity is already forced. That's the whole parity trick. No magic, just accounting.
Let an endpoint mean “the last kept position is ”, where means we have kept nothing yet.
From endpoint :
and is either ? or the character .
This gives a DAG/NFA whose path labels are exactly the obtainable strings. The obvious DP over endpoints double-counts like hell, because the same output string can be embedded in multiple ways.
Suppose after producing the same prefix, endpoints are both possible. If
then endpoint is redundant. Why? Use the embedding ending at , delete the whole substring , and then do whatever the embedding from was going to do. So every continuation from is already a continuation from .
So after every transition, we sort possible endpoints and delete every endpoint dominated by an earlier one.
After reduction, at most two endpoints remain.
Assume three endpoints survived. Since survived, does not dominate , so is false. Therefore has no ? and an odd number of fixed 1s.
Similarly, since survived, does not dominate , so also has no ? and odd fixed 1 parity.
Their union has no ? and
so is true. That means dominates , contradiction. Boom. The huge subset construction collapses to pairs.
A state is a reduced set of active endpoints, either
Let be the number of distinct suffixes we can append from active endpoint set .
The empty suffix is allowed iff some endpoint can stop:
For each bit , collect every endpoint reachable by appending from any , reduce the collected endpoints by dominance, and recurse. Prefixes starting with 0 and 1 are disjoint, so
Missing transitions contribute .
To make transitions fast, precompute : the reduced set of endpoints reachable from singleton state by appending bit . Then for a pair state, the next state is just the reduction of
There are possible reduced states, each has two transitions, and each transition handles at most four endpoints.
Prefix counts give in .
Precomputing all costs
The memoized DP visits at most states, with work per transition, so the total complexity is
per test case, with
memory. Since , this fits easily.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
const int MOD = 998244353;
int T;
cin >> T;
while (T--) {
int n;
string s;
cin >> n >> s;
vector<int> pref1(n + 1), prefq(n + 1);
for (int i = 1; i <= n; i++) {
pref1[i] = pref1[i - 1] + (s[i - 1] == '1');
prefq[i] = prefq[i - 1] + (s[i - 1] == '?');
}
auto ok = [&](int l, int r) -> bool {
if (l > r) return true;
int qs = prefq[r] - prefq[l - 1];
int ones = pref1[r] - pref1[l - 1];
return qs > 0 || ones % 2 == 0;
};
auto can_be = [&](int pos, int bit) -> bool {
return s[pos - 1] == '?' || s[pos - 1] == char('0' + bit);
};
vector<array<array<int, 2>, 2>> go(n + 1);
for (int u = 0; u <= n; u++) {
for (int bit = 0; bit < 2; bit++) {
array<int, 2> keep = {-1, -1};
int sz = 0;
for (int v = u + 1; v <= n; v++) {
if (!can_be(v, bit) || !ok(u + 1, v - 1)) continue;
bool dominated = false;
for (int i = 0; i < sz; i++) {
if (ok(keep[i] + 1, v)) {
dominated = true;
break;
}
}
if (!dominated && sz < 2) keep[sz++] = v;
}
go[u][bit] = keep;
}
}
auto reduce_small = [&](array<int, 4> vals, int cnt) -> array<int, 2> {
sort(vals.begin(), vals.begin() + cnt);
array<int, 2> res = {-1, -1};
int sz = 0;
int last = -2;
for (int i = 0; i < cnt; i++) {
int v = vals[i];
if (v < 0 || v == last) continue;
last = v;
bool dominated = false;
for (int j = 0; j < sz; j++) {
if (ok(res[j] + 1, v)) {
dominated = true;
break;
}
}
if (!dominated && sz < 2) res[sz++] = v;
}
return res;
};
int width = n + 2;
vector<int> memo((n + 1) * width, -1);
auto id = [&](int a, int b) -> int {
return a * width + (b + 1);
};
auto dfs = [&](auto&& self, int a, int b) -> int {
int &ret = memo[id(a, b)];
if (ret != -1) return ret;
ll ans = 0;
if (ok(a + 1, n) || (b != -1 && ok(b + 1, n))) ans = 1;
for (int bit = 0; bit < 2; bit++) {
array<int, 4> vals = {-1, -1, -1, -1};
int cnt = 0;
for (int i = 0; i < 2; i++) {
if (go[a][bit][i] != -1) vals[cnt++] = go[a][bit][i];
}
if (b != -1) {
for (int i = 0; i < 2; i++) {
if (go[b][bit][i] != -1) vals[cnt++] = go[b][bit][i];
}
}
array<int, 2> nxt = reduce_small(vals, cnt);
if (nxt[0] != -1) {
ans += self(self, nxt[0], nxt[1]);
ans %= MOD;
}
}
ret = int(ans % MOD);
return ret;
};
cout << dfs(dfs, 0, -1) << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
const int MOD = 998244353;
int T;
cin >> T;
while (T--) {
int n;
string s;
cin >> n >> s;
vector<int> pref1(n + 1), prefq(n + 1);
for (int i = 1; i <= n; i++) {
pref1[i] = pref1[i - 1] + (s[i - 1] == '1');
prefq[i] = prefq[i - 1] + (s[i - 1] == '?');
}
auto ok = [&](int l, int r) -> bool {
if (l > r) return true;
int qs = prefq[r] - prefq[l - 1];
int ones = pref1[r] - pref1[l - 1];
return qs > 0 || ones % 2 == 0;
};
auto can_be = [&](int pos, int bit) -> bool {
return s[pos - 1] == '?' || s[pos - 1] == char('0' + bit);
};
vector<array<array<int, 2>, 2>> go(n + 1);
for (int u = 0; u <= n; u++) {
for (int bit = 0; bit < 2; bit++) {
array<int, 2> keep = {-1, -1};
int sz = 0;
for (int v = u + 1; v <= n; v++) {
if (!can_be(v, bit) || !ok(u + 1, v - 1)) continue;
bool dominated = false;
for (int i = 0; i < sz; i++) {
if (ok(keep[i] + 1, v)) {
dominated = true;
break;
}
}
if (!dominated && sz < 2) keep[sz++] = v;
}
go[u][bit] = keep;
}
}
auto reduce_small = [&](array<int, 4> vals, int cnt) -> array<int, 2> {
sort(vals.begin(), vals.begin() + cnt);
array<int, 2> res = {-1, -1};
int sz = 0;
int last = -2;
for (int i = 0; i < cnt; i++) {
int v = vals[i];
if (v < 0 || v == last) continue;
last = v;
bool dominated = false;
for (int j = 0; j < sz; j++) {
if (ok(res[j] + 1, v)) {
dominated = true;
break;
}
}
if (!dominated && sz < 2) res[sz++] = v;
}
return res;
};
int width = n + 2;
vector<int> memo((n + 1) * width, -1);
auto id = [&](int a, int b) -> int {
return a * width + (b + 1);
};
auto dfs = [&](auto&& self, int a, int b) -> int {
int &ret = memo[id(a, b)];
if (ret != -1) return ret;
ll ans = 0;
if (ok(a + 1, n) || (b != -1 && ok(b + 1, n))) ans = 1;
for (int bit = 0; bit < 2; bit++) {
array<int, 4> vals = {-1, -1, -1, -1};
int cnt = 0;
for (int i = 0; i < 2; i++) {
if (go[a][bit][i] != -1) vals[cnt++] = go[a][bit][i];
}
if (b != -1) {
for (int i = 0; i < 2; i++) {
if (go[b][bit][i] != -1) vals[cnt++] = go[b][bit][i];
}
}
array<int, 2> nxt = reduce_small(vals, cnt);
if (nxt[0] != -1) {
ans += self(self, nxt[0], nxt[1]);
ans %= MOD;
}
}
ret = int(ans % MOD);
return ret;
};
cout << dfs(dfs, 0, -1) << '\n';
}
}