卡特兰数

hdu 5184

题目大意：一个n，然后一串括号，括号数量 大于0小于等于n，问你在给出了前 个括号的情况下，长度为n的规则括号序列有多少种。
卡特兰数一眼题-----钟涛大佬。
题目的输入不一定保证是规则括号序列，所以如果n是奇数或者存在右括号的数量多于左括号的数量，或者左括号的数量大于n的一半是一定不能构成规则括号的。
统计左括号数量为 x ，右括号的数量为 y。总的方案数相当于从(1,1)到的路径数，经过对角线的方案数相当于从(1,1)到 的路径数。左括号看成是 1 ，意思是向右走1步，左括号看成是 0 ，意思是向上走1步，总的方案数就是 .组合数用逆元来求。涉及到减法，结果需要加上模数再取模，避免出现负数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,maxn=1e6;
ll f[maxn];
ll qpow(ll a,ll b) {
    ll res=1;
    while(b) {
        if(b&1)    res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main() {
    ll n;
    char s[maxn+1];
    f[0]=1;
    for(int i=1;i<=maxn;++i)    f[i]=f[i-1]*i%mod;
    while(~scanf("%d%s",&n,s)){
        ll x=0,y=0,ans=0,flag=0;
        for(int i=0;s[i];++i) {
            if(s[i]=='(')    ++x;
            else ++y;
            if(y>x) {
                flag=1;
                break;
            }
        }
        if(n&1||flag||x>n/2){
            puts("0");
            continue;
        }
        n/=2;
        ans=f[(n<<1)-x-y]*qpow(f[n-x]*f[n-y]%mod,mod-2)%mod-f[(n<<1)-x-y]*qpow(f[n-x-1]*f[n-y+1]%mod,mod-2)%mod;
        printf("%lld\n",(ans+mod)%mod);               
    }
}

hdu 5177暂时看不懂。