前言

很好的一道卡特兰数入门题，不板也不难

题目

HDU

讲解

括号匹配是经典的卡特兰数问题

首先我们把无解与唯一解的情况特判出来，再考虑问题

传统的卡特兰数的括号匹配对应的模型为从\((0,0)\)走到\((n,n)\)而不越过\(y=x\)的方案数

而现在我们的起点变成了\((a,b)\)，其中\(a\)为已经给出的左括号\((\)的数量，\(b\)为右括号的数量

而终点变成了\((n/2,n/2)\)(这里的\(n\)为题目给出的\(n\))

根据传统卡特兰数的求解方式，我们发现不考虑限制，到\((n/2,n/2)\)的方案数减去到\((n/2-1,n/2+1)\)的方案数即为答案

所以最终答案为\(C_{n/2-a+n/2-b}^{n/2-a}-C_{n/2-1-a+n/2+1-b}^{n/2-1-a}\)

这个式子未免太过冗长

我们令\(A=n/2-a,B=n/2-b\)

化简后为\(C_{A+B}^{A}-C_{A+B}^{A-1}\)

代码

LL qpow(LL x,int y)
{
LL ret = 1;
while(y){if(y & 1) ret = ret * x % MOD;x = x * x % MOD;y >>= 1;}
return ret;
}
int fac[MAXN],ifac[MAXN];
void pre(int x)
{
fac[0] = 1;
for(int i = 1;i <= x;++ i) fac[i] = 1ll * fac[i-1] * i % MOD;
ifac[x] = qpow(fac[x],MOD-2);
for(int i = x-1;i >= 0;-- i) ifac[i] = 1ll * ifac[i+1] * (i + 1) % MOD;
}
int check()
{
int cnt = 0;
for(int i = 1;i <= lena;++ i)
if(a[i] == ‘(‘) cnt++;
else
{
cnt--;
if(cnt <0) return -1;
}
if(lena + cnt > n) return -1;
return cnt;
}
LL C(int x,int y)
{
if(x return 1ll * fac[x] * ifac[y] % MOD * ifac[x-y] % MOD;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
pre(1000000);
while(~scanf("%d",&n))
{
scanf("%s",a+1);
lena = strlen(a+1);
int c = check();
if((n & 1) || c <0) {Put(0,‘\n‘);continue;}
if(!c && lena == n){Put(1,‘\n‘);continue;}
int A = (n-lena-c) / 2,B = (n-lena-c) / 2 + c;//‘(‘,‘)‘
Put((C(A+B,A) - C(A+B,A-1) + MOD) % MOD,‘\n‘);
}
return 0;
}