题目链接：https://codeforces.com/problemset/problem/785/D
题解：
首先很好想的，如果我们预处理出每个 "(" 左边有 $x$ 个 "("，以及右边有 $y$ 个 ")"，那么就有式子如下：
若 $x+1 \le y$：$C_{x}^{0} C_{y}^{1} + C_{x}^{1} C_{y}^{2} + \cdots + C_{x}^{x} C_{y}^{x+1} = \sum_{i=0}^{x} C_{x}^{i} C_{y}^{i+1}$
若 $x+1 > y$：$C_{x}^{0} C_{y}^{1} + C_{x}^{1} C_{y}^{2} + \cdots + C_{x}^{y-1} C_{y}^{y} = \sum_{i=0}^{y-1} C_{x}^{i} C_{y}^{i+1}$
然后算一下，哦哟 $O(n^2)$ 的优秀算法，GG，想了半天也不知道咋优化，看了题解才知道是“范德蒙德恒等式”：
$C_{m+n}^{k} = \sum_{i=0}^{k} C_{m}^{i} C_{n}^{k-i}$
那么就有：
$\sum_{i=0}^{x} C_{x}^{i} C_{y}^{i+1} = \sum_{i=0}^{x} C_{x}^{i} (C_{y-1}^{i} + C_{y}^{i}) = \sum_{i=0}^{x} C_{x}^{i} C_{y-1}^{i} + \sum_{i=0}^{x} C_{x}^{i} C_{y}^{i} = \sum_{i=0}^{x} C_{x}^{x-i} C_{y-1}^{i} + \sum_{i=0}^{x} C_{x}^{x-i} C_{y}^{i} = C_{x+y-1}^{x} + C_{x+y}^{x} = C_{x+y}^{x+1}$
类似的，也有：
$\sum_{i=0}^{y-1} C_{x}^{i} C_{y}^{i+1} = $
Codeforces 785D - Anton and School - 2 - [范德蒙德恒等式]
原文：https://www.cnblogs.com/dilthey/p/10692881.html