将（视为1，）是为-1，则是合法字符串的充要条件为
- 任意位置前缀和非负
- 总和为0
对于本题，条件2显然满足，考虑条件1
设插入位置原本前缀和为x
- 插入()后变为x,x+1,x
- 插入)(后变为x，x-1，x
即分为了三段
fi,j 表示i次插入，原数字为j合法的概率
插入（）：
fn,x=p∗∑i=0n−1∑j=0n−i−1Cn−1i∗Cn−i−1j∗fi,x∗fj,x∗fn−1−i−j,x+1
插入）（：
fn,x=(1−p)∗∑i=0n−1∑j=0n−i−1Cn−1i∗Cn−i−1j∗fi,x∗fj,x∗fn−1−i−j,x−1
至此，我们得到了一个
O(n4) 的做法
考虑优化
考虑把j的枚举去除
把有关i的放一起
（以()为例）
fn,x=(1−p)∗∑i=0n−1Cn−1i∗fi,x∗∑j=0n−i−1Cn−i−1j∗fj,x∗fn−1−i−j,x+1
设
gn,x=∑j=0nCnj∗fj,x∗fn−j,x+1所以
fn,x=p∗∑i=0n−1Cn−1i∗fi,x∗gn−i−1,x对于)(，新开一个h，十分类似
hn,x=∑j=0nCnj∗fj,x∗fn−j,x−1
所以
fn,x=∑i=0n−1Cn−1i∗fi,x∗(p∗gn−i−1,x+(1−p)∗hn−i−1,x)生成方案有
1∗3∗5∗...∗(2n−1) 种，最后除掉即为答案