Bracket Insertion
Contest: VK Cup 2022 - Отборочный раунд (Engine)
Difficulty rating: 2700
Tags: combinatorics, dp, math, trees

Vika likes playing with bracket sequences. Today she wants to create a new bracket sequence using the following algorithm. Initially, Vika's sequence is an empty string, and then she will repeat the following actions $$$n$$$ times:

- Choose a place in the current bracket sequence to insert new brackets uniformly at random. If the length of the current sequence is $$$k$$$, then there are $$$k+1$$$ such places: before the first bracket, between the first and the second brackets, $$$\ldots$$$, after the $$$k$$$-th bracket. In particular, there is one such place in an empty bracket sequence.
- Choose string "()" with probability $$$p$$$ or string ")(" with probability $$$1 - p$$$ and insert it into the chosen place. The length of the bracket sequence will increase by $$$2$$$.

A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into it. For example, sequences "(())()", "()", and "(()(()))" are regular, while ")(", "(()", and "(()))(" are not.

Vika wants to know the probability that her bracket sequence will be a regular one at the end. Help her and find this probability modulo $$$998\,244\,353$$$ (see Output section).

Input format:
The only line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 500$$$; $$$0 \le q \le 10^4$$$). Here $$$n$$$ is equal to the number of bracket insertion operations, and the probability that Vika chooses string "()" on every step of the algorithm is equal to $$$p = q \cdot 10^{-4}$$$.

Output format:
Print the probability that Vika's final bracket sequence will be regular, modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. 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} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first example, Vika will get a regular bracket sequence () with probability $$$p = \frac{3}{4}$$$, and she will get an irregular bracket sequence )( with probability $$$1 - p = \frac{1}{4}$$$. The sought probability is $$$\frac{3}{4}$$$, and $$$249\,561\,089 \cdot 4 \equiv 3 \pmod{998\,244\,353}$$$.

In the second example, the sought probability is $$$\frac{11}{25}$$$.

Example input:
1 7500

Example output:
249561089

Example input:
2 6000

Example output:
519087064

Editorial:
Instead of looking at a probabilistic process, we can consider all possible ways of inserting brackets. There are $$$1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n - 1) = (2n - 1)!!$$$ ways of choosing places, and $$$2^n$$$ ways of choosing "()" or ")(" at every point. Let $$$r$$$ be the sum of $$$p^k \cdot (1-p)^{n-k}$$$ over all such ways that lead to a regular bracket sequence, where $$$k$$$ is the number of strings "()" inserted during the process (and $$$n - k$$$ is then the number of strings ")(" inserted). Then, $$$\frac{r}{(2n - 1)!!}$$$ is the answer to the problem.
Consider the sequence of "prefix balances" of the bracket sequence. The first (empty) prefix balance is $$$0$$$, and each successive balance is $$$1$$$ larger than the previous one if the next bracket is '(', and $$$1$$$ smaller if the bracket is ')'.
Initially, when the bracket sequence is empty, the sequence of prefix balances is $$$[0]$$$. Whenever we insert "()" into the bracket sequence in a place with prefix balance $$$x$$$, essentially we are replacing $$$x$$$ with $$$[x, x + 1, x]$$$ in the sequence of prefix balances. Whenever we insert ")(" instead, that's equivalent to replacing $$$x$$$ with $$$[x, x - 1, x]$$$.
A bracket sequence is regular if and only if its corresponding sequence of prefix balances does not have any negative integers (and ends with $$$0$$$; however, this is guaranteed in our setting).
Thus, we can reformulate the problem as follows:
• Initially, we have an integer array $$$[0]$$$.
• $$$n$$$ times, we choose an integer from the array uniformly at random.
• Say this integer is $$$x$$$, then we replace $$$x$$$ with $$$[x, x + 1, x]$$$ with probability $$$p$$$, and with $$$[x, x - 1, x]$$$ with probability $$$1 - p$$$.
• What is the probability that the sequence will not contain negative integers at any point?
Let $$$f(n, x)$$$ be the sought probability multiplied by $$$(2n - 1)!!$$$ if we start with $$$[x]$$$ Here, we multiply by $$$(2n-1)!!$$$ to simplify the formulas, and to keep thinking about "numbers of ways" instead of "probabilities", as described in the first paragraph of this tutorial.
The base cases are $$$f(0, x) = 1$$$ if $$$x \ge 0$$$, and $$$f(0, x) = 0$$$ otherwise. When $$$n > 0$$$:
What does this formula mean? Essentially, since we start with an array of a single integer $$$[x]$$$, the first operation has to be applied to $$$x$$$. After that, once $$$x$$$ gets replaced with $$$[x, x \pm 1, x]$$$, $$$i$$$ operations will be applied to the left $$$x$$$ (including everything produced from it), $$$j$$$ operations will be applied to $$$x \pm 1$$$ (again, together with its production), and $$$n - 1 - i - j$$$ operations will be applied to the right $$$x$$$ (and to its production).
Thus, we can find the sum over $$$i$$$ and $$$j$$$ of the product of the corresponding values of $$$f$$$ and the binomial coefficients: since the sequences of $$$i$$$, $$$j$$$, and $$$n - 1 - i - j$$$ operations can be interleaved arbitrarily, we have $$$\binom{n-1}{i}$$$ ways to choose the positions of $$$i$$$ operations applied to the left $$$x$$$ in the global sequence of $$$n-1$$$ operations, and then $$$\binom{n-1-i}{j}$$$ ways to choose the positions of $$$j$$$ operations applied to $$$x \pm 1$$$ out of the remaining $$$n - 1 - i$$$ positions in the global sequence.
This results in an $$$O(n^4)$$$ solution, since there are $$$O(n^2)$$$ values of $$$f$$$ to calculate, and each of them is calculated in $$$O(n^2)$$$.
To optimize it, let's rewrite the formula a little bit by moving the loop over $$$j$$$ outside:
Now, let's introduce an auxiliary function:
Now, let's rewrite the formula for $$$f$$$ using $$$g$$$:
Now, both $$$g(n, x)$$$ and $$$f(n, x)$$$ can be computed in $$$O(n)$$$ time, resulting in an $$$O(n^3)$$$ solution.