题目链接：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，想了半天也不知道咋优化，看了题解才知道是“范德蒙德恒等式”：
$\sum_{i=0}^{r} C_{m}^{i} C_{n}^{r-i} = C_{m+n}^{r}$
以及它的一个推导等式：
$\sum_{i=0}^{m} C_{m}^{i} C_{n}^{r+i} = C_{m+n}^{m+r}$
① 直接用推导等式可以得到：
$\sum_{i=0}^{x} C_{x}^{i} C_{y}^{i+1} = C_{x+y}^{x+1}$
而 ② 则用范德蒙德恒等式得到：
$\sum_{i=0}^{y-1} C_{x}^{i} C_{y}^{i+1} = \sum_{i=0}^{y-1} C_{x}^{i} C_{y}^{y-1-i} = C_{x+y}^{y-1}$
综上，就变成了：对于每个 "("，假设其左边还有 $x$ 个 "("，右边有 $y$ 个 ")"，那么对于答案的贡献：
① 若 $x+1 \le y$，则为 $C_{x+y}^{x+1}$
② 若 $x+1 > y$，则为 $C_{x+y}^{y-1}$
只要预处理出阶乘和阶乘的逆元，那么每次算 $C_{n}^{r}$ 就是 $O(1)$ 的。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
const int maxn=2e5+; char s[maxn];
int n,x[maxn],y[maxn]; ll fpow(ll a,ll n)
{
ll res=, base=a%mod;
while(n)
{
if(n&) res*=base, res%=mod;
base*=base, base%=mod;
n>>=;
}
return res%mod;
}
ll inv(ll a){return fpow(a,mod-);} ll fac[maxn],fac_inv[maxn];
ll C(ll n,ll r)
{
ll res=fac[n];
res*=fac_inv[r], res%=mod;
res*=fac_inv[n-r], res%=mod;
return res;
} int main()
{
fac[]=, fac_inv[]=inv(fac[]);
for(int i=;i<maxn;i++) fac[i]=fac[i-]*i%mod, fac_inv[i]=inv(fac[i]); scanf("%s",s+), n=strlen(s+); x[]=;
for(int i=;i<=n;i++) x[i]=x[i-]+(s[i-]=='(');
y[n]=;
for(int i=n-;i>;i--) y[i]=y[i+]+(s[i+]==')');
//for(int i=1;i<=n;i++) printf("%d %d\n",x[i],y[i]); ll ans=;
for(int i=;i<=n;i++)
{
if(s[i]!='(') continue;
if(y[i]<=) continue;
if(x[i]+<=y[i])
ans+=C(x[i]+y[i],x[i]+), ans%=mod;
else
ans+=C(x[i]+y[i],y[i]-), ans%=mod;
}
cout<<ans<<endl;
}