题目链接

转自

给你一个字符串问你能构造多少RSBS。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}

LL lcm(LL a,LL b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

const int N =2e5+32;

LL inv[N],fac[N],ans;

int n;

const LL mod = 1e9+7;

void it(){

	fac[0]=1;

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

	inv[n]=powmod(fac[n],mod-2,mod);

	for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;

}

char a[N];

int x,y;

LL C(int x,int y){

	if(x<0||y<0)return 0;

	return fac[x]*inv[y]%mod*inv[x-y]%mod;

}

int main(){

	ios::sync_with_stdio(false);

	cin>>a+1;

	n=strlen(a+1);

	it();

	for(int i=1;i<=n;i++)x+=(a[i]==')');

	for(int i=1;i<=n;i++){

		if(a[i]=='('){

			y++;

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

			ans%=mod;

		}else x--;

	}

	cout<<ans;

	return 0;

}