见过很多次但是都没有切掉的题目。

显然通过题目的方式生成括号序列的方案数有 $\prod\limits_{i=1}^n 2i-1$ 种，考虑 DP 求出方案数然后最后再除以所有的方案数。

假设 $\texttt{(}$ 是 $1$，$\texttt{)}$ 是 $-1$ 那么容易想到一个合法的括号序列的充要条件就是前缀和恒不小于 $0$ 而且以 $0$ 结尾。

如果我们在某一个括号序列后面添加 $\texttt{()}$ 或者 $\texttt{)(}$，那么如果原本的前缀和为 $x$ 添加后就会多出 $x+1,x$ 或者 $x-1,x$。

考虑设状态 $f_{i,j}$ 表示经过 $i$ 次操作之后初始的前缀和为 $j$ 的方案数。

那么对于插入 $\texttt{()}$，有转移：

$f_{n,x}\gets f_{n,x}+\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}p \dbinom{n-1}{i} \dbinom{n-i-1}{j} f_{i,x}\cdot f_{j,x+1}\cdot f_{n-i-j-1,x}$

对于插入 $\texttt{)(}$，有转移：

$f_{n,x}\gets f_{n,x}+\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}(1-p) \dbinom{n-1}{i} \dbinom{n-i-1}{j} f_{i,x}\cdot f_{j,x-1}\cdot f_{n-i-j-1,x}$

其转移的思路是通过插入的 $2$ 个字符将整个字符串拆分为 $3$ 个部分，分别是第 $1$ 个字符之前、两个字符中间和第 $2$ 个字符之后。

因为题目只要求在最后合法，所以插入的顺序可以随意发挥，所以方案数需要乘上组合数。

把和 $j$ 有关的从上面的式子中提出来，得到：

$f_{n,x}=\sum\limits_{j=0}^{n-1}\dbinom{n-1}{j}\cdot\left[p\cdot f_{j,x+1}+(1-p)\cdot f_{j,x-1}\right]\cdot \sum\limits_{i=0}^{n-j-1}\dbinom{n-j-1}{i}\cdot f_{i,x}\cdot f_{n-i-j-1,x}$

那么把后面的依托提前预处理出来，最后输出的时候除以总共的方案数就行了，时间复杂度为 $O(n^3)$。