codeforce 785D - Anton and School - 2【组合数学】

题目大意

给定一个括号序列
可以删除某一些括号
使得该序列成为一个
长度为偶数
前n/2为 “(”
后n/2为“)”
的匹配括号串
问删除的方案数

题目分析

枚举作为最后一个( 的 符号，计算以这个符号为节点的方案数
前缀和算出该符号之前的 ( 个数， 后缀和算出该符号右边的)个数
由于，当前符号必须选中
所以，想到于在之前的符号中选取 i个，之后的符号中选取i+1个
令x = l[i] 表示左边的左括号个数
y=r[i] 表示右边的有括号个数

当前 符号的方案数 C（x,i）*C(y,i+1)的求和
然后通过范德蒙恒等式转换一下就好啦

代码详解

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define sc(x) scanf("%d",&x)
#define pt(x) printf("%d\n",x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=2e5+50;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
ll fpow(ll n,ll k,ll p=mod){ll r=1;for(;k;k>>=1){if(k&1)r = r*n%p;n=n*n%p;}return r;}
ll inv(ll n,ll p=mod){return fpow(n,p-2,p);}
ll n,m;
ll fact[maxn];
void init()
{
    fact[0]=1;
    for(int i=1;i<maxn;i++)
        fact[i]=fact[i-1]*i%mod;
}
ll C(ll n, ll m)
{
    ll t = fact[n]*inv(fact[m])%mod;
       t = t * inv(fact[n-m])%mod;
    return t;
}
ll l[maxn],r[maxn];
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    ll ans=0;
    init();
  // for(int i=1;i<10;i++) cout<<fact[i]<<" ";
    for(int i=0;i<s.size();i++)
    {
        l[i]=l[i-1];
        if(s[i]=='(') l[i]++;
    }
    for(int i=s.size()-1;i>=0;i--)
    {
        r[i]=r[i+1];
        if(s[i]==')')r[i]++;
    }
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(')
        {
            // int t= min(l[i],r[i]);
             ans=(ans+C(l[i]+r[i]-1,l[i]))%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}