AcWing 3420. 括号序列
原题链接
困难
作者:
我已经不想再做刺客了
,
2022-04-05 21:30:21
,
所有人可见
,
阅读 213
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
const int N=5005;
int f[N][N],n;
char s[N];
int cal(){
for(int i=1;i<=n;i++){
if(s[i]=='('){
for(int j=1;j<=n;j++)
f[i][j]=f[i-1][j-1];
}
else{
f[i][0]=(f[i-1][0]+f[i-1][1])%p;
for(int j=1;j<=n;j++)
f[i][j]=(f[i][j-1]+f[i-1][j+1])%p;
}
}
for(int i=0;i<=n;i++)if(f[n][i])return f[n][i];
}
signed main(){
scanf("%s",s+1);
n=strlen(s+1);
f[0][0]=1;
int l=cal();
reverse(s+1,s+1+n);
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=n;i++)s[i]='('+')'-s[i];
int r=cal();
printf("%d",l*r%p);
}