\(\text{link}\) 。也是一道非常巧妙的 \(\texttt{dp}\) 。
容易想到把括号变成 \(\pm 1\)。考虑括号序列合法等价于前缀和 \(\ge 0\)，我们可以想加入 \(()\) 或 \()(\) 对前缀的影响。
设加入的位置的前一位前缀和为 \(x\)，则加入 \(()\) 相当于把 \(x\) 替换为 \([x,x+1,x]\)，加入 \()(\) 相当于把 \(x\) 替换为 \([x,x-1,x]\)。
则原问题等价于初始给定一个集合 \(S={0}\)，有 \(n\) 次操作，每次等概率地选择集合中的一个元素 \(x\)，并有 \(p\) 的概率把 \(x,x+1\) 加入 \(S\)，有 \(1-p\) 的概率把 \(x,x-1\) 加入 \(S\)，求\(n\) 次操作后 \(S\) 中所有元素非负的概率。
显然概率转方案，最终除以 \((2n-1)!!\)。
令 \(f_{n,x}\) 表示进行了 \(n\) 次操作，初始在集合中的数为 \(x\) 的方案数。
则 \(f_{n,x}=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1-i}\dbinom{1}{1}\)