Codeforces Round #404 (Div. 2) D. Anton and School - 2

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接

转自

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

#include<bits/stdc++.h>#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_backusing 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;
}