solution
最终括号串形如：(***(...)(...)***(...))，或者 ((...)(...)***(...)***)，或者 ((...)(...)***(...))，就是说中间可有可无，两边只留一个。
令 \(st_{l,r}\) 表示 \([l,r]\) 是否可以全为星号。
令 \(f_{l,r}\) 表示 (...)***(...)...(...)(...)，强制两边都是括号，转移等会。
令 \(g_{l,r}\) 表示 (...)，就是外面套一层括号之后里面合法的方案数。
\(f_{l,r}=\sum_{l\leq k\leq r}g_{l,k}\left(f_{k+1,r}+\sum_{k<p<r}st_{k+1,p}f_{p+1,r}\right).\)
\(g_{l,r}=[a_l='('][a_r=')'](f_{l+1,r-1}+\sum_{l+1\leq k\leq r-1}st_{l+1,k}f_{k+1,r-1}+\sum_{l+1<k\leq r-1}f_{l+1,k-1}st_{k,r-1}).\)
标签：...,LGP7914,题解,sum,括号,2021,leq From： https://www.cnblogs.com/caijianhong/p/solution-P7914.html