CodeForces 785D Anton and School – 2

枚举，容斥原理，范德蒙恒等式。

先预处理每个位置之前有多少个左括号，记为$L[i]$。

每个位置之后有多少个右括号，记为$R[i]$。

然后枚举子序列中第一个右括号的位置，计算这个括号的第一个右括号的方案数。

即在它左边取$k$个左括号，在右边取$k-1$个右括号都是合法的方案，这个东西可以用范德蒙恒等式化成一个组合数以及容斥原理计算。

范德蒙恒等式：http://blog.csdn.net/acdreamers/article/details/31032763

#include <cstdio>
#include <cmath>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL; char s[200010];
long long L[200010],R[200010];
LL fac[200010];
long long mod = 1e9+7;void init()
{
    int i;
    fac[0] =1;
    for(i =1; i <= 200000; i++)
        fac[i] = fac[i-1]*i%mod;
}
LL pow(LL a, LL b)
{
    LL tmp = a % mod, ans =1;
    while(b)
    {
        if(b &1)  ans = ans * tmp % mod;
        tmp = tmp*tmp % mod;
        b >>=1;
    }
    return  ans;
}
LL C(LL n, LL m)
{
    if(m>n||m<0)return 0;
    return  fac[n]*pow(fac[m]*fac[n-m],mod-2)%mod;
}   int main()
{
init();
scanf("%s",s);
int len = strlen(s);for(int i=1;i<=len;i++)
{
L[i] = L[i-1];
if(s[i-1]=='(') L[i]++;
}for(int i=len;i>=1;i--)
{
R[i] = R[i+1];
if(s[i-1]==')') R[i]++;
}long long ans = 0;for(int i=1;i<=len;i++)
{
if(s[i-1]=='(') continue;
if(L[i]==0) continue;long long m,k1,k2;m = min(L[i],R[i]);
if(m==0) k1=1;
else k1 = C(L[i]+R[i],m);m = min(L[i],R[i]-1);
if(m==0) k2=1;
else k2 = C(L[i]+R[i]-1,m);long long k = (k1-k2+mod)%mod;
ans = ( ans + k ) %mod;
}printf("%lld\n",ans);return 0;
}