锐客网

  1. 首页 > it技术 > >

HDU 5184 Brackets (卡特兰数)

数学

题目： LINK
【HDU 5184 Brackets (卡特兰数)】题意： 定义合法的括号序列如下：
● 空序列是合法括号序列
● 如果s是一个合法括号序列，那么(s)也是合法括号序列
● 如果a和b是合法括号序列，那么ab也是合法括号序列
● 没有其它情况是合法括号序列
给定已知括号序列的前一部分，问可以构造出多少合法序列。
可以提前判断出一些非法的情况，比如n为奇数，给定部分括号非法。之后求合法学列数量。
其实就是求出卡特兰数。
结果ans = C(a+b, b) - C(a+b, b-1) , (设a=剩余要填的')'的数量， b=剩余要填的'('的数量)
-------------------------
关于卡特兰数，一个例子是有n个1,m个-1(n>=m)，要求用这些1和-1排列形成n+m长度的排列，要求前i项的和sum[i]>=0 (1<=i<=n+m),这个排列的方案数目就是卡特兰数。方案数应该是C(n+m, m) - C(n+m, m-1)
可以看出本题和上面的例子很相像。当然这只是卡特兰数的一个例子，应该还有好多用途。
关于上面结果的证明过程：可以转化为在平面坐标系中，从(0, 0)走到(n, m)每次向上走或者向右走，且不能越过x=y的直线的方法数。把(0, 0) 和(n, m)都往下移一个单位成为(0, -1), (n, m-1). 从(0, 0)走到(n, m)的非法数目 = (0, -1)到(n, m-1)过程中至少一点和x=y相交的走法数。ans = 总数目 - 非法数目 = C(n+m, m) - 非法数目。根据对称性，(0, -1)到(n, m-1)过程中至少一点和x=y相交的走法数 = (-1, 0)到(n, m-1)的方法数。所以ans = C(n+m, m) - C(n+m, m-1)。
-------------------------
回到原题，原题结果的求法同样放到坐标系中去，合法序列数目为(x, y) ==> (m, m)且不越过x=y的数目,x为已有'('的数目，y为已有')'的数目，m = n/2; 通过平移和对称性，我们可以转化为求(0, 0) ==> (m-y, m-x)不越过x=y直线的方法数,就可以利用上面求出的公式。
会用到有除法的取模，所以要求出逆元。


/* *********************************************** Author: Napoleon Mail: tyfdream@163.com Created Time: 2015-03-11 16:04:59 Problem: CB_32_C.cpp ************************************************ */ #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1000000000 typedef __int64 LL; #define N 1100111 #define mod 1000000007 LL n, a, b, fac[N]; char str[N]; void init() { fac[0] = 1; for(int i = 1; i <= 1000111; i++) { fac[i] = (fac[i-1] * i) % mod; } } LL pow_(LL a, LL b, LL m) { LL ret = 1; while(b) { if(b&1) { ret *= a; ret %= m; } a *= a; a %= m; b >>= 1; } return ret; } LL Inv(LL a, LL m) { return pow_(a, m - 2, m); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif // ONLINE_JUDGE init(); while(scanf("%I64d", &n) != EOF) { scanf("%s", str); if(n&1) { puts("0"); continue; } a = b = 0; int flag = 0; for(int i = 0; str[i]; i ++) { if(str[i] == '(') a ++; else b ++; if(b > a) flag = 1; } LL m = n / 2; if(flag || a > m || b > m || b > a) { puts("0"); continue; } a = m - a; b = m - b; swap(a, b); //a >= b LL ans = (a-b+1)*fac[a+b] % mod; ans = ans * Inv(a+1, mod) % mod; ans = ans * Inv(fac[a], mod) % mod; ans = ans * Inv(fac[b], mod) % mod; cout<



    推荐阅读


    上一篇：okhttp|浅析OkHttp使用-请求分发流程

    下一篇：Android Parcel分析