这是一位数学小萌新看 oi-wiki 的一点点收获。
二项式定理
二项式定理是组合数学中很基础且很重要的定理，它的式子为：
\((a+b)^n= \sum_{i=0}^n \binom{n}{i} a^i b^{n-i}\)
可以通过归纳法剖析 \((a+b)^n\) 的过程证明其正确性。
范德蒙德卷积：
\(\large \sum_{i=0}^k \binom{n}{i} \binom{m}{k-i}=\binom{n+m}{k}\)
证明就可以用二项式定理，可参考 oi-wiki。
推论 1：
\(\large \sum_{i=-r}^s \binom{n}{r+i}\binom{m}{s-i}=\binom{n+m}{r+s}\)
证明：
\(i\) 从 \(0\) 开始就能转化到范德蒙德卷积的基本形式。
推论 2：
\(\large\sum_{i=1}^n \binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}\)
证明：
\(\large\sum_{i=1}^n \binom{n}{i}\binom{n}{i-1}=\sum_{i=0}^{n-1} \binom{n}{i}\binom{n}{i+1}= \sum_{i=0}^{n-1} \binom{n}{i}\binom{n}{n-i-1}=\binom{2n}{n-1}\)
考虑组合的意义，将 \(2n\) 个球分成两组再选等价于直接从 \(2n\) 个球里面选，所以
\(\large \sum_{i=0}^{n-1} \binom{n}{i}\binom{n}{n-i-1}=\binom{2n}{n-1}\)
CF785D
我们考虑枚举每一个中间点算贡献，对于任意一个中间位置 \(i\) 有
\(\large \sum_{k=1}^n \binom{pre_i}{k}\binom{suf_i}{k}\)
\(pre,suf\) 分别表示左括号的前缀和，右括号的后缀和。
但是发现会出现重复的子序列，那么我们如果遇到一个左括号就定它是最后一个左括号，遇到一个右括号就定它为第一个右括号，但是发现子序列的唯一性，只需要枚举最后一个左括号就行了，那么对于任意的位置 \(i\) 对答案的贡献，有
\(\large \sum_{k=1}^n \binom{pre_{i-1}}{k-1}\binom{suf_{i+1}}{k}\)
我们将式子变为
\(\large \sum_{k=1}^n \binom{pre_{i-1}}{pre_{i-1}-k+1}\binom{suf_{i+1}}{k}\)
通过考虑其组合意义（卷积）可以发现这个式子的贡献就是 \(\dbinom{pre_{i-1}+suf{i+1}}{pre_{i-1}+1}\)，于是本题解决。
第二类斯特林数
咕咕咕