这题说的给了一个整数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 ;
}
05-06 22:26