CF1264D（组合数）

把云剪贴板里的东西发出来顺便复习一下

---

考虑如何贪心确定一个序列的深度？

可以考虑最左边的左括号，最右边的有括号匹配，然后扔掉匹配的两个括号后继续做，这样是最大的。

考虑一对括号如何会产生贡献？

手玩一下能发现，当 \((i,j)\) ， \(i\) 的左边左括号数 = \(j\) 右边右括号数，且 s[i]=='(' , s[j]==')' ，就会有贡献。

但是要枚举两个，比较不可做，如何简化问题？

考虑换个枚举，贡献只算在右括号上，设 s[i]=='(' 。那么 \(i\) 右边的 ) 比 \(i\) 左边的 ( 严格少， \(i\) 就一定会被匹配一次。

设 \(i\) 左边的 ( 为 \(A\) 个，? 为 \(C\) 个；设右边的 ) 为 \(B\) 个，? 为 \(D\) 个。

\(i\) 的贡献为：

\[\sum_{x=1}^C \sum_{y=1}^D \binom{C}{x}\binom{D}{y} [x+A>y+B] \]

这个 \(x+A>y+B\) 相当于 \(x-y>B-A\) ，减法没法化简，但是可以转化成加法：

\[\sum_{x=1}^C \sum_{y=1}^D \binom{C}{C-x}\binom{D}{y} [x+A>y+B] \]

用 \(x\) 替换 \(C-x\)

\[\sum_{x=1}^C \sum_{y=1}^D \binom{C}{x}\binom{D}{y} [C-x+A>y+B] \]

\[\sum_{x=1}^C \sum_{y=1}^D \binom{C}{x}\binom{D}{y} [x+y\le A+C-B-1] \]

\[\sum_{k=0}^{A+C-B-1} \sum_{x=1}^C \sum_{y=1}^D \binom{C}{x}\binom{D}{y}[x+y=k] \]

后面柿子成为了范德蒙德卷积，直接替换掉两个循环：

\[\sum_{k=0}^{A+C-B-1} \binom{C+D}{k} \]

由于枚举的 \(i\) 只能为 )　或　? ，因此 \(C+D\) 只有两种可能取值。

然后处理两个组合数前缀和就能算了。