有一个空括号串 \(s\)，接下来进行 \(n\) 次操作：
-
假设当前括号序列长度为 \(l\)，则在产生的 \(l+1\) 个空位中随机选择一个
-
在当前空位以 \(p\) 的概率插入 \(\texttt{()}\)，以 \(1-p\) 的概率插入 \(\texttt{)(}\)
求所有操作结束后 \(s\) 是合法括号串的概率，对 \(998244353\) 取模。
考虑一个括号串合法，当且仅当将 \(\texttt{(}\) 看成 \(1\)，\(\texttt{)}\) 看成 \(-1\) 后：
-
\(\sum\limits_{i=1}^{|s|} s_i = 0\)
-
\(\sum\limits_{i=1}^{p} s_i \geq 0\)
容易发现，在题目的限制下，第一个限制一定是自动满足的。
对于修改操作，我们发现加入的部分不会影响两边的前缀和。
为了判断第二个性质，我们考虑刻画可重集 \(S\)，维护 \(s\) 的前缀和。
初始时，\(S\) 中只有一个 \(0\)，接下来每次操作可以抽象成：
-
从 \(S\) 中随机选择一个元素 \(x\)
-
在 \(S\) 中以 \(p\) 的概率加入 \(x\) 和 \(x+1\)，以 \(1-p\) 的概率加入 \(x\) 和 \(x-1\)
则最终我们希望 \(S\) 中的所有元素都 \(\geq 0\)。
考虑概率这个东西显然很不好刻画，我们把它转成方案数。
首先，总共的方案数一定是 \(\prod\limits_{i=1}^{n} (2i - 1)\)，接下来我们算合法方案。
你发现新加入的数相当于另一个初始状态，考虑据此设计 dp。
我们令 \(dp_{x,t}\) 表示初始 \(S\) 中只有一个 \(x\)，操作 \(t\) 次后仍然合法的方案数。
显然，我们的答案为 \(dp_{0,n}\)，接下来我们考虑怎么转移。
不妨先考虑以 \(p\) 的概率加入 \(x\) 和 \(x+1\) 这种情况。
此时，我们加入后会构成三个基本状态，包括两个 \(x\) 和一个 \(x+1\)。
接下来我们就是在这 \(3\) 个状态的基础上进行扩展，也就是说：
第二种情况：
这看起来很显然，于是你尝试转移，发现直接枚举复杂度 \(O(n^5)\) 炸了。
然而你发现 \(t_1 + t_2 + t_3 = t-1\)，所以我们不需要枚举 \(t\)。
然而这还是 \(O(n^4)\)，根本过不去。
你发现这东西一项一项做，卷积就是 \(O(n^3)\) 的了。