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.
For a fixed string, define and . only goes up, and only goes down. So the only prefix position that really matters is the first one where .
For binary strings with zeroes and ones, the count with has a tiny closed form: if max(x,y) >= k, every string works; otherwise the answer is . This is the Catalan/reflection trick hiding under a fake moustache.
Handle b > a by enumerating the first differing position . You only care about positions where , force , and keep the prefix before equal to .
After fixing that lexicographic prefix, if it already reached , the rest of the problem is just: how many completions make the suffix after the first hit have ? Use the same closed form, but with a known prefix already attached to that suffix.
If the fixed prefix has not reached , enumerate the future character that first reaches . A 0-hit forces the number of added zeroes before it. A 1-hit needs the previous part to have LNDS exactly , counted as ways(>=k-1)-ways(>=k). For fixed length this is constant except one boundary row, so prefix sums over the suffix closed form give .
Let .
The main trap is thinking we need to remember all possible split points. We do not. For a complete string , define
As increases, never decreases, and never increases. So if is the first position where , then the string is valid exactly when . Any earlier split has a bad left side, and any later split has an even smaller right side. That turns the split condition into: find the first prefix hit, then check the suffix after it.
Counting strings with LNDS at least
Let be the number of binary strings with zeroes, ones, and LNDS at least .
If , every string works, because all zeroes or all ones already form a nondecreasing subsequence. Otherwise and , and the reflection argument on the zero/one lattice path gives
.
So:
Here when is outside .
Known prefix version
We also need this version a lot. Suppose a known prefix has:
and we append an unknown string with zeroes and ones. Let be the number of completions whose total LNDS is at least .
There are four cases:
That is the whole G function.
Lexicographic enumeration
Enumerate the first position where differs from . This only matters when , because then we force . The prefix before is fixed equal to .
Let this forced prefix be . If its counts already exceed the required number of zeroes or ones, skip it.
Now there are two cases.
Case 1: the fixed prefix already hit
Let be the first position inside where the prefix LNDS reaches .
Then the suffix after starts with a known string: the remaining part of after , followed by the still-free positions. We compute the known suffix prefix's zero count and LNDS , then add
,
where are the remaining zeroes and ones.
For substring LNDS queries, use the binary formula. If D_i=#0-#1 on prefixes, then for substring ,
f(l,r)=#1(l,r)+\max_{t\in[l,r+1]}D_t-D_l.
A sparse table over answers that max query.
Case 2: the fixed prefix has not hit
Let the fixed prefix have zeroes and LNDS . Define
So is how many future ones can extend the current best subsequence to , and is how many future zeroes are needed to reach using zeroes.
Now enumerate the character that first makes the prefix reach .
If the hit character is 0
A zero can only help the all-zero subsequence. Therefore before this hit zero, we must have added exactly zeroes.
If we added ones before it, we also need , otherwise the prefix would already have reached via ones.
The number of possible pre-hit strings is
.
Then the remaining suffix must independently have LNDS at least , so multiply by .
If the hit character is 1
Appending a one extends any existing nondecreasing subsequence, so before the hit we need LNDS exactly .
For a pre-hit block of length with zeroes and ones, the count is
.
This difference is nonzero only inside the rectangle
.
For fixed , inside that rectangle it is usually
.
The only special boundary is , where the at least k-1 count becomes all strings instead of . So we add the correction
for that one value of .
To sum suffix contributions fast, precompute
.
Then for a fixed remaining total length , any range of possible suffix zero counts is queried in .
Overall, each lexicographic prefix spends linear work over possible hit lengths, so the whole test case is . The memory is also for the suffix prefix sums, which is fine for under the given summed limits.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MAXN = 10000;
vector<int> fact, invFact;
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 C(int n, int r) {
if (n < 0 || r < 0 || r > n) return 0;
return (ll)fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
int subMod(int a, int b) {
a -= b;
if (a < 0) a += MOD;
return a;
}
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
fact.assign(MAXN + 1, 1);
invFact.assign(MAXN + 1, 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;
int tc;
cin >> tc;
while (tc--) {
int x, y, k;
string a;
cin >> x >> y >> k >> a;
int n = x + y;
vector<int> prefZ(n + 1), prefO(n + 1), prefL(n + 1), firstHit(n + 1, -1), D(n + 1);
int bestD = 0;
for (int i = 0; i < n; i++) {
prefZ[i + 1] = prefZ[i] + (a[i] == '0');
prefO[i + 1] = prefO[i] + (a[i] == '1');
D[i + 1] = D[i] + (a[i] == '0' ? 1 : -1);
bestD = max(bestD, D[i + 1]);
prefL[i + 1] = prefO[i + 1] + bestD;
firstHit[i + 1] = firstHit[i];
if (firstHit[i + 1] == -1 && prefL[i + 1] >= k) firstHit[i + 1] = i + 1;
}
vector<int> lg(n + 2);
for (int i = 2; i <= n + 1; i++) lg[i] = lg[i / 2] + 1;
int levels = lg[n + 1] + 1;
vector<vector<int>> st(levels, vector<int>(n + 1));
st[0] = D;
for (int j = 1; j < levels; j++) {
for (int i = 0; i + (1 << j) <= n + 1; i++) {
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
auto rangeMaxD = [&](int l, int r) -> int {
int len = r - l + 1;
int j = lg[len];
return max(st[j][l], st[j][r - (1 << j) + 1]);
};
auto fSub = [&](int l, int r) -> int {
if (l > r) return 0;
int ones = prefO[r + 1] - prefO[l];
return ones + rangeMaxD(l, r + 1) - D[l];
};
auto F = [&](int z, int o) -> int {
if (z < 0 || o < 0) return 0;
if (max(z, o) >= k) return C(z + o, z);
return C(z + o, k);
};
auto G = [&](int rx, int ry, int need, int Z, int L) -> int {
if (rx < 0 || ry < 0) return 0;
if (need <= 0) return C(rx + ry, rx);
if (L + ry >= need || Z + rx >= need) return C(rx + ry, rx);
if (Z + rx + ry < need) return 0;
return C(rx + ry, need - Z);
};
vector<vector<int>> prefF(n + 1);
for (int total = 0; total <= n; total++) {
prefF[total].assign(total + 2, 0);
for (int z = 0; z <= total; z++) {
int val = F(z, total - z);
int nxt = prefF[total][z] + val;
if (nxt >= MOD) nxt -= MOD;
prefF[total][z + 1] = nxt;
}
}
auto sumF = [&](int total, int l, int r) -> int {
if (total < 0) return 0;
l = max(l, 0);
r = min(r, total);
if (l > r) return 0;
return subMod(prefF[total][r + 1], prefF[total][l]);
};
auto countNoHit = [&](int Z, int L, int X, int Y) -> int {
int A = k - L;
int B = k - Z;
int res = 0;
if (Y >= 1) {
int Y1 = Y - 1;
for (int m = 0; m <= X + Y - 1; m++) {
int lo = max(0, m - Y1);
int hi = min(X, m);
int l = max(lo, m - (A - 1));
int r = min(hi, B - 1);
if (l > r) continue;
int base = subMod(C(m, B - 1), C(m, B));
int totalRem = X + Y1 - m;
int suffixSum = sumF(totalRem, X - r, X - l);
res = (res + (ll)base * suffixSum) % MOD;
int u0 = m - (A - 1);
if (l <= u0 && u0 <= r) {
int corr = subMod(C(m, u0), C(m, B - 1));
int val = F(X - u0, Y1 - m + u0);
res = (res + (ll)corr * val) % MOD;
}
}
}
if (B >= 1 && X >= B) {
int u = B - 1;
int maxV = min(Y, A - 1);
for (int v = 0; v <= maxV; v++) {
int m = u + v;
int ways = subMod(C(m, u), C(m, u + 1));
int val = F(X - B, Y - v);
res = (res + (ll)ways * val) % MOD;
}
}
return res;
};
int ans = 0;
for (int p = 0; p < n; p++) {
if (a[p] != '0') continue;
int usedZ = prefZ[p];
int usedO = prefO[p] + 1;
int remZ = x - usedZ;
int remO = y - usedO;
if (remZ < 0 || remO < 0) continue;
int prefAfterFlipL = prefL[p] + 1;
int add = 0;
if (firstHit[p] != -1 || prefAfterFlipL >= k) {
int e = (firstHit[p] != -1 ? firstHit[p] : p + 1);
int suffixZ = 0, suffixL = 0;
if (e != p + 1) {
suffixZ = prefZ[p] - prefZ[e];
suffixL = fSub(e, p - 1) + 1;
}
add = G(remZ, remO, k, suffixZ, suffixL);
} else {
add = countNoHit(usedZ, prefAfterFlipL, remZ, remO);
}
ans += add;
if (ans >= MOD) ans -= MOD;
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MAXN = 10000;
vector<int> fact, invFact;
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 C(int n, int r) {
if (n < 0 || r < 0 || r > n) return 0;
return (ll)fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
int subMod(int a, int b) {
a -= b;
if (a < 0) a += MOD;
return a;
}
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
fact.assign(MAXN + 1, 1);
invFact.assign(MAXN + 1, 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;
int tc;
cin >> tc;
while (tc--) {
int x, y, k;
string a;
cin >> x >> y >> k >> a;
int n = x + y;
vector<int> prefZ(n + 1), prefO(n + 1), prefL(n + 1), firstHit(n + 1, -1), D(n + 1);
int bestD = 0;
for (int i = 0; i < n; i++) {
prefZ[i + 1] = prefZ[i] + (a[i] == '0');
prefO[i + 1] = prefO[i] + (a[i] == '1');
D[i + 1] = D[i] + (a[i] == '0' ? 1 : -1);
bestD = max(bestD, D[i + 1]);
prefL[i + 1] = prefO[i + 1] + bestD;
firstHit[i + 1] = firstHit[i];
if (firstHit[i + 1] == -1 && prefL[i + 1] >= k) firstHit[i + 1] = i + 1;
}
vector<int> lg(n + 2);
for (int i = 2; i <= n + 1; i++) lg[i] = lg[i / 2] + 1;
int levels = lg[n + 1] + 1;
vector<vector<int>> st(levels, vector<int>(n + 1));
st[0] = D;
for (int j = 1; j < levels; j++) {
for (int i = 0; i + (1 << j) <= n + 1; i++) {
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
auto rangeMaxD = [&](int l, int r) -> int {
int len = r - l + 1;
int j = lg[len];
return max(st[j][l], st[j][r - (1 << j) + 1]);
};
auto fSub = [&](int l, int r) -> int {
if (l > r) return 0;
int ones = prefO[r + 1] - prefO[l];
return ones + rangeMaxD(l, r + 1) - D[l];
};
auto F = [&](int z, int o) -> int {
if (z < 0 || o < 0) return 0;
if (max(z, o) >= k) return C(z + o, z);
return C(z + o, k);
};
auto G = [&](int rx, int ry, int need, int Z, int L) -> int {
if (rx < 0 || ry < 0) return 0;
if (need <= 0) return C(rx + ry, rx);
if (L + ry >= need || Z + rx >= need) return C(rx + ry, rx);
if (Z + rx + ry < need) return 0;
return C(rx + ry, need - Z);
};
vector<vector<int>> prefF(n + 1);
for (int total = 0; total <= n; total++) {
prefF[total].assign(total + 2, 0);
for (int z = 0; z <= total; z++) {
int val = F(z, total - z);
int nxt = prefF[total][z] + val;
if (nxt >= MOD) nxt -= MOD;
prefF[total][z + 1] = nxt;
}
}
auto sumF = [&](int total, int l, int r) -> int {
if (total < 0) return 0;
l = max(l, 0);
r = min(r, total);
if (l > r) return 0;
return subMod(prefF[total][r + 1], prefF[total][l]);
};
auto countNoHit = [&](int Z, int L, int X, int Y) -> int {
int A = k - L;
int B = k - Z;
int res = 0;
if (Y >= 1) {
int Y1 = Y - 1;
for (int m = 0; m <= X + Y - 1; m++) {
int lo = max(0, m - Y1);
int hi = min(X, m);
int l = max(lo, m - (A - 1));
int r = min(hi, B - 1);
if (l > r) continue;
int base = subMod(C(m, B - 1), C(m, B));
int totalRem = X + Y1 - m;
int suffixSum = sumF(totalRem, X - r, X - l);
res = (res + (ll)base * suffixSum) % MOD;
int u0 = m - (A - 1);
if (l <= u0 && u0 <= r) {
int corr = subMod(C(m, u0), C(m, B - 1));
int val = F(X - u0, Y1 - m + u0);
res = (res + (ll)corr * val) % MOD;
}
}
}
if (B >= 1 && X >= B) {
int u = B - 1;
int maxV = min(Y, A - 1);
for (int v = 0; v <= maxV; v++) {
int m = u + v;
int ways = subMod(C(m, u), C(m, u + 1));
int val = F(X - B, Y - v);
res = (res + (ll)ways * val) % MOD;
}
}
return res;
};
int ans = 0;
for (int p = 0; p < n; p++) {
if (a[p] != '0') continue;
int usedZ = prefZ[p];
int usedO = prefO[p] + 1;
int remZ = x - usedZ;
int remO = y - usedO;
if (remZ < 0 || remO < 0) continue;
int prefAfterFlipL = prefL[p] + 1;
int add = 0;
if (firstHit[p] != -1 || prefAfterFlipL >= k) {
int e = (firstHit[p] != -1 ? firstHit[p] : p + 1);
int suffixZ = 0, suffixL = 0;
if (e != p + 1) {
suffixZ = prefZ[p] - prefZ[e];
suffixL = fSub(e, p - 1) + 1;
}
add = G(remZ, remO, k, suffixZ, suffixL);
} else {
add = countNoHit(usedZ, prefAfterFlipL, remZ, remO);
}
ans += add;
if (ans >= MOD) ans -= MOD;
}
cout << ans << '\n';
}
}