CodeForces 785D Anton and School - 2

题目链接：​​http://codeforces.com/contest/785/problem/D​​​
题意：给你一个字符串只包含’(‘和’)’，让你重新组成一个字符串，这个字符串的左边必须全部为）右边必须全部为（，问你有多少种这样的字符串
解析：先前缀和的方式处理出到第i个字符位置他前面有多少个’(‘，他后面有多少个’)’，处理好以后，剩下的就是枚举位置i，然后组合数运算

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int maxn = 2e5+100;
const int inf = 0x7fffffff;
const int mod = 1e9+7;
typedef long long ll;
char a[maxn];
int sum1[maxn],sum2[maxn];
ll jiec[maxn];
void init(int n)
{
    jiec[0] = 1;
    for(int i=1;i<=n;i++)
        jiec[i] = (jiec[i-1]*i)%mod;
    memset(sum1,0,sizeof(sum1));
    memset(sum2,0,sizeof(sum2));
}
ll qpow(ll x,ll n)
{
    int res = 1;
    while(n)
    {
        if(n&1)
            res = res*x%mod;
        x = x*x%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll a)
{
    return qpow(a,mod-2);
}
ll slove(int a,int b)
{
    if(b>a)
        return 0;
    if(b==0)
        return 1;
    return (jiec[a]*inv((jiec[a-b]*jiec[b])%mod))%mod;
}
int main()
{
    scanf("%s",a+1);
    int len = strlen(a+1);
    init(len);
    for(int i=1;i<=len;i++)
    {
        if(a[i]=='(')
            sum1[i] = sum1[i-1]+1;
        else
            sum1[i] = sum1[i-1];
        if(a[len-i+1]==')')
            sum2[len-i+1] = sum2[len-i+2]+1;
        else
            sum2[len-i+1] = sum2[len-i+2];
    }
    ll ans = 0;
    for(int i=1;i<=len;i++)
    {
        if(a[i]=='(')
        {
            int t1 = sum1[i];
            int t2 = sum2[i];
            ans = (ans+slove(t1+t2-1,t2-1))%mod;
        }
    }
    printf("%I64d\n",ans);
    return 0;
}