CF2150G.Counting Is Fun: The Finale

zabutom, Dubmood - Track Tracking

⠀

给定三个正整数 $x$、$y$ 和 $k$。

同时给定一个二进制字符串 $a$（$|a| = x + y$）。

请计算满足下列条件的二进制字符串 $b$ 的个数，结果对 $998\,244\,353$ 取模：

• $b$ 中恰好有 $x$ 个 $0$。
• $b$ 中恰好有 $y$ 个 $1$。
• 存在一个整数 $i$（$1 \leq i \leq x + y - 1$），使得 $\min \left( f(b_1 b_2 \ldots b_i), f(b_{i+1} b_{i+2} \ldots b_{x+y})\right) \geq k$，其中 $f(s)$ 表示字符串 $s$ 的最长不下降子序列的长度。
• $b$ 的字典序大于 $a$。

【注：】
$^*$ 二进制字符串指只由字符 $0$ 和 $1$ 组成的字符串。

$^\dagger$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可以通过删除 $b$ 的若干（可以为零或全部）元素得到。例如，$\mathtt{1011101}$ 的子序列有 $\mathtt{0}$、$\mathtt{1}$、$\mathtt{11111}$、$\mathtt{0111}$，但没有 $\mathtt{000}$ 和 $\mathtt{11100}$。

$^\ddagger$ 如果字符串 $p$ 满足以下条件之一被称为字典序大于字符串 $q$：

• $q$ 是 $p$ 的前缀，且 $p \ne q$；
• 在 $p$ 和 $q$ 第一个不同的位置，$p$ 的该字符比 $q$ 的该字符大。

每组测试包含多组测试用例。第一行包含整数 $t$（$1 \le t \le 5000$），表示测试用例数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含三个整数 $x$、$y$ 和 $k$（$1 \le x, y \le 5000$，$1 \leq k < x + y$）。

每组测试用例的第二行包含一个长度为 $x+y$ 的二进制字符串 $a$，仅包含字符 $0$ 和 $1$。

保证所有测试用例中 $x$ 的和不超过 $5000$，$y$ 的和也不超过 $5000$。

对于每组测试用例，输出一个整数，表示满足条件的二进制字符串数量，对 $998\,244\,353$ 取模。

对于第一个测试用例，有两个满足条件的字符串：$\mathtt{01}$ 和 $\mathtt{10}$。

对于第三个测试用例，有四个满足条件的字符串：$\mathtt{0110}$、$\mathtt{1001}$、$\mathtt{1010}$ 和 $\mathtt{1100}$。

由 ChatGPT 5 翻译