This is the easy version of "Binary Stack", the only difference between the easy and hard versions are the constraints.
You have a binary array $a$ and a binary stack $s$, we define the operation $X(a,s)$ as the following: For each element of $a$ from left to right if it's equal to the top of the stack $s$, pop that top element from the stack, otherwise do nothing. For example if $a=110$ and $s=100$, then $X(a,s)$ will go as follow:
You're give $a$ and $s$, if $a$ was shuffled randomly, what is the probability that at the end of the operation $X(a,s)$ s will be empty module $M=998244353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1}\mod{M}$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.
The first line contains 2 integers $|a|$ and $|s|$($1 \le |s| \le |a| \le 5000$), the length of $a$ and the length of $s$.
The second line contains $a$.
The third line contains $s$, where the leftmost element is the top of the stack $s$.
Print a single integer, the probability as stated above.
For the first example, there are 3 different arrays that can result from shuffling $a$: $011$, $101$ and $110$, only the first 2 will result in an empty stack, so the answer is $\frac{2}{3}$.
| Input | Output |
|---|---|
3 2 011 01 Copy
|
665496236 Copy
|
7 5 1010011 10110 Copy
|
827116750 Copy
|
If the number of zeros or the number of ones in $a$ is less than that number in $s$ then the answer is $0$.
For now let's find the number of possible arrays $a$ that will end up with an empty stack $s$, let's build the array $a$ from scratch, first let $a=s$, so every one and every zero in $a$ will remove an element from $s$, and these are the only elements in $a$ that will remove an element from $s$. After doing that let's say we still need to add $x$ zeros and $y$ ones to $a$, let's try to add them to $a$ such that they won't remove any element from $s$.
Let's call the ones and zeros in $a$ that will remove an element from $s$ good, the only possible way to add a zero that doesn't alter $s$ is to put it behind a good one, and to add a one we should put it behind a good zero, or we can put them at the end of $a$. Let's say we want to add $p$ zeros and $q$ ones to the end of $a$, then we will have to put $x-p$ zeros and $y-q$ ones before the good ones and zeros, this can be calculated using binomial coefficients, with a method called stars and bars.
So the overall solution is for each pair of $p$ and $q$ calculate the number of such arrays $a$ using binomial coefficients, and then divide that sum by the total number of possible arrays $a$ that you can get from shuffling it to get the final probability.