codeforces 785D D. Anton and School

题目链接：http://codeforces.com/problemset/problem/785/D

题意：给你一个只包含'('和')'的字符串，然后问他的子序列中有多少满足前一半是左括号，后一半是右括号。

分析：看到题就想到是组合数学，对于一个左括号，他能影响到的右括号就是他后边的，因此，你需要求前缀和和后缀和，来这样来求组合数。现在我们枚举左括号，当枚举到他时，代表他一定被选，前缀和为n，后缀和为m，然后在他前边选i=0到min（n,m）-1个，在他后边选前边数+1个。然后就是C(n-1,i)*C(m,i+1) ,也就是C(n-1,i)+C(m,m-i-1);求和即为C(n+m-1,m-1)，然后用卢卡斯定理求即可，注意存n！还有求逆元。

AC代码：

#include<bits/stdc++.h>
using namespace std;

long long mod=1e9+7;
char s[200005];
int a[200005];
int b[200005];
long long num[200005];
long long qpow(long long x,long long n){
    if(n==0) return 1;
    long long ans=1;
    x=x%mod;
    while(n!=0){
        if(n&1) {
            ans=ans*x%mod;
        }
        x=x*x%mod;
        n=n/2;
    }
    return ans;
}
long long Cn(long long n,long long m){
    if(n<m) return 0;
    if(n==m) return 1;
    if(m>n-m) m=n-m;

    return (num[n]*qpow(num[n-m]*num[m],mod-2))%mod;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    num[0]=1;
    for(long long i=1;i<=200000;i++){
        num[i]=num[i-1]*i%mod;
    }
    cin>>s;
    int d=strlen(s);
    int num1=0,num2=0;
    for(int i=0;i<d;i++){
        if(s[i]=='('){
            num1++;
        }
        a[i]=num1;
    }
    for(int i=d-1;i>=0;i--){
        if(s[i]==')'){
            num2++;
        }
        b[i]=num2;
    }
    long long result=0;
    for(int i=0;i<d;i++){
        if(s[i]=='('){
           result=(result+Cn(a[i]+b[i]-1,b[i]-1))%mod;
        //cout<<result<<endl;
        }
    }
    cout<<result<<endl;
    return 0;
}