这题说的给了一个整数n 和一串的括号， 那么要我们计算 最后有n/2对括号的 方案数有多少。
我们可以先预先判断一些不可能组成正确括号对的情况，
然后我们可以将这个问题转化到二维平面上， 令 m = n/2 ，L 为左括号的个数 R为右括号的个数 可以知道还有 m - L 个左括号没用， 有m-R个右括号没用，令他们分别我p=m-R,q=m-L, 然后机的就是 （0，0）点到 (p,q)点 不跨过x=y这条线的方案数，那么我们可以这样做，将 （0，0） 向下移动 1 个单位，（0,-1）-》》》》》(p,q-1) , 假设如果非法那么必须会经过（d,d）这个点，我们知道从(0,-1)到（d,d）和（-1,0）到（d,d）的方案数是一样的，那么我们就知道了从(0,1) 出发的非法的方案数为 （-1，0） 到(p.q-1) 的方案数，那么最终的答案就是 C(p+q,q)-C(p+q,q-1);
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const int maxn = +;
typedef long long LL;
const LL mod = ;
LL dp[maxn];
LL mdp[maxn];
LL vdp[maxn];
char str[maxn];
void gcd(LL a, LL b, LL &d, LL &x, LL &y){
if(!b) {d=a; x= ; y =;}
else{gcd(b,a%b,d,y,x); y -= x*(a/b);}
}
LL inv(LL a, LL n){
LL d,x,y;
gcd(a,n,d,x,y);
return d== ? (x+n)%n:-;
}
int main()
{
dp[]=;
for(LL i=; i<=; ++i){
dp[i]=(dp[i-]* i)%mod;
}
int n;
while(scanf("%d",&n)==){
scanf("%s",str); if(n%){
printf("0\n"); continue;
}
LL m = n/;
int len =strlen(str);
LL L=,R=;
for(int i=; i<len; ++i){
if(str[i]=='(') L++;
else if(str[i]==')')R++;
if(L<R){
L=-; break;
}
}
if(L==-||L>m){
printf("0\n");continue;
}
if(L==R&&L+R==n){
printf("1\n");continue;
}
L=m - L;
R=m - R;
LL d0 = L;
L=R; R=d0;
LL d1 = inv(L+,mod); LL d2 = inv(dp[L],mod);
LL d3 = inv(dp[R],mod); LL ans =( ( ( ( ( ( ( ( L-R+ )*d1 )%mod) * d2 )%mod) * d3)%mod) * dp[L+R])%mod;
printf("%I64d\n",ans);
} return ;
}