CF1781F Bracket Insertion （学习笔记）
shaun2000
·
·
个人记录
将（视为1，）是为-1，则是合法字符串的充要条件为
- 任意位置前缀和非负
- 总和为0
对于本题，条件2显然满足，考虑条件1
设插入位置原本前缀和为x
- 插入()后变为x,x+1,x
- 插入)(后变为x，x-1，x
即分为了三段
插入（）：
$ f_{n,x}= p*\sum^{n-1}_{i=0}\sum_{j=0}^{n-i-1} C_{n-1}^{i}*C_{n-i-1}^{j} * f_{i,x}*f_{j,x}*f_{n-1-i-j,x+1}
插入）（：
f_{n,x}= (1-p)*\sum^{n-1}_{i=0}\sum_{j=0}^{n-i-1} C_{n-1}^{i}*C_{n-i-1}^{j} * f_{i,x}*f_{j,x}*f_{n-1-i-j,x-1}
至此，我们得到了一个 O(n^4) 的做法
考虑优化
考虑把j的枚举去除
把有关i的放一起
（以()为例）
f_{n,x}= (1-p)*\sum^{n-1}_{i=0}C_{n-1}^{i}*f_{i,x}*\sum_{j=0}^{n-i-1} C_{n-i-1}^{j} * f_{j,x}*f_{n-1-i-j,x+1}
设 g_{n,x}=\sum_{j=0}^{n} C_{n}^{j}*f_{j,x}*f_{n-j,x+1}
所以 f_{n,x}= p*\sum^{n-1}_{i=0}C_{n-1}^{i}*f_{i,x}*g_{n-i-1,x}
对于)(，新开一个h，十分类似
h_{n,x}=\sum_{j=0}^{n} C_{n}^{j}*f_{j,x}*f_{n-j,x-1}
所以f_{n,x}=\sum^{n-1}_{i=0}C_{n-1}^{i}*f_{i,x}*(p*g_{n-i-1,x} + (1-p)*h_{n-i-1,x})
复杂度 O(n^3)
生成方案有 1*3*5*...*(2n-1) 种，最后除掉即为答案