Codeforces 785D Anton and School

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

【题目大意】

　　给出一个只包含左右括号的串，请你找出这个串中的一些子序列，
　　要求满足"(((())))"，即左边全是左括号右边全是右括号且数量相等的形式。
　　求这样的子序列的数量。

【题解】

　　我们枚举每个断点(，计算当这个位置作为最后一个左括号时候的方案数
　　设左边有x个左括号，右边有y个右括号，那么统计答案为ΣC(x,i)*C(y,i+1)
　　又有C(y,i+1)=C(y,y-1-i)，所以答案为ΣC(x,i)*C(y,y-1-i)=C(x+y,y-1)

【代码】

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=400010;

const LL mod=1000000007;

LL f[N],rf[N];

int l[N],r[N],m,n,k;

LL inv(int a,int m){return(a==1?1:inv(m%a,m)*(m-m/a)%m);}

LL C(int n,int m){if(n<m||m<0)return 0;return f[n]*rf[m]%mod*rf[n-m]%mod;}

void init(n){

    f[0]=1LL;for(int i=1;i<=n;i++)f[i]=(LL)f[i-1]*i%mod;

    rf[n]=inv(f[n],mod);

    for(int i=n;i;i--)rf[i-1]=(LL)rf[i]*i%mod;

}

char s[N];

int sl[N],sr[N];

int main(){

    init(400000);

    scanf("%s",s+1);

    int n=strlen(s+1);

    for(int i=1;i<=n;i++)sl[i]=sl[i-1]+(s[i]=='(');

    for(int i=n;i;i--)sr[i]=sr[i+1]+(s[i]==')');

    LL ans=0;

    for(int i=1;i<=n;i++)if(s[i]=='('){

        int x=sl[i-1],y=sr[i+1];

        ans=(ans+C(x+y,y-1))%mod;

    }printf("%lld\n",ans);

    return 0;

}

巴特西

Codeforces 785D Anton and School - 2（组合数）

最新文章

热门文章