P11487 「Cfz Round 5」Gnirts 10

In Memory of $\text{F}\rule{66.8px}{6.8px}$.

Let's keep the problem statement simple. - Given $n, m$, and a binary string $S$ of length $n + m$. - For a binary string $T$, define $f(T)$ as the length of the longest prefix of $S$ that is a subsequence $^\dagger$ of $T$. - For every binary string $T$ that **contains exactly $\bm n$ $\tt 1$s and $\bm m$ $\tt 0$s**, compute the sum of $f(T)$. The answer should be modulo $2933256077^\ddagger$. $\dagger$: Note that a subsequence does not need to be contiguous. In other words, $a$ is a subsequence of $b$ if and only if $a$ can be obtained by deleting $\geq 0$ characters from $b$. Note that the empty string is always a subsequence of any string. $\ddagger$: The modulus is a prime number.

The first line contains two integers $n, m$. The second line contains a binary string $S$ of length $n + m$.

Output a single integer, representing the result modulo $2933256077$.

#### Sample Explanation #1 The only possible sequence is the common sequence $\texttt{0}$. Since there are exactly 3 different $T$s ($\tt 110, 101, 011$), the answer is $1 \times 3 = 3$. #### Constraints For all test cases, it is guaranteed that $1 \leq n, m \leq 3\times 10^6$. **Subtasks are used in this task.** - Subtask 0 (13 points): $\max(n, m) \leq 5$. - Subtask 1 (13 points): $\max(n, m) \leq 100$. - Subtask 2 (34 points): $\max(n, m) \leq 3\times 10^3$. - Subtask 3 (40 points): No further restrictions.