卡特兰数，棋盘问题的推导
题目意思：
定义了括号的合法排列方式，给出一个排列的前一段，问能组成多少种合法的排列
本题要点：
1、推导过程：
n对括号排列，左括号看做是在棋盘沿着 x 方向走， 右括号看做是在棋盘沿着 y 方向走.
前面的任意k个括号，左括号的数 >= 右括号的数。相当于在棋盘走，没有超过 y = x 这条线。
这就是卡特兰数的定义。
2、现在问题有所加深：题目给出一部分括号
排列的总长度为 n ，左右括号各为 m = n / 2 个。当给定的排列方式完全合法的时候，剩下需要排列的左右括号的数量就已经确定了，
而在排列的过程中，左括号要始终大于等于右括号的数量。设现在有 a 个左括号， b 个右括号，那么这个就可以当做从（ a ， b ）点
到 （ m ， m ）点且不越过直线 y = x 的种类数。
将图像下移，则可认为是从（ 0 ， 0 ）点到 （ p ， q ）点且不越过直线 y = x + q - p 的种类数。
显然，这里的p, q 满足关系： a + p = b + q == n / 2。
3、 参考组合数学教材中，棋盘问题的卡特兰数的推导。
从 (0, 0) 到 (p, q) 这一点，总的走法 c(p + q, p), 然而，没有过线 y = x + q - p 的走法有 c(p + q, p - 1)。
相当于从 (0, 0) 到 (p, q) 这一点的每一种走法，对应于一个从点 (0, 0) 走到 点(p - 1, q + 1) 的一种走法。
而且这些走法是一一对应的。 显然，从点 (0, 0) 走到 点(p - 1, q + 1)， 在 p + q 中选出 p - 1 个，数值为 c(p + q, p - 1)。
（推导是类似的，把线 y = x + q - p 沿着y正方向移动一个单位，变为 y = x + q - p + 1）
c(p + q, p) - c(p + q, p - 1)
= ((p + q)! * (q - p + 1)) / ((q + 1)! * p!)
4、逆元：
这里的mod 是素数，可以用费马小定理来求 阶乘 k! 模mod的逆元。
5、逼逼这么多，都是参考这位老哥的 点这里
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int MaxN = 1000010;
const ll mod = 1000000007;
ll fac[MaxN];
char s[MaxN];
int n;void init()
{
fac[0] = fac[1] = 1;for(int i = 2; i < MaxN; ++i){
fac[i] = fac[i - 1] * i % mod; }
}ll qucikPow(ll a, ll p)
{
ll tmp = a, ans = 1;tmp %= mod;while(p){
if(p & 1){
ans = ans * tmp % mod;}tmp = tmp * tmp % mod;p >>= 1;}return ans;
}void solve()
{
int p = 0, q = 0, len = strlen(s);for(int i = 0; i < len; ++i){
if(s[i] == '('){
++p;}else{
++q;}if(q > p){
printf("0\n");return;}}if(q > p){
return;}p = n / 2 - p, q = n / 2 - q;if(p < 0 || q < 0){
printf("0\n");return;}ll r1 = qucikPow(fac[p], mod - 2), r2 = qucikPow(fac[q + 1], mod - 2);;//（（ p + q ）！*（ q - p + 1 ））/（（q + 1）！* p！）ll res = q - p + 1;res = res * fac[p + q] % mod;res = res * r1 % mod;res = res * r2 % mod;printf("%lld\n", res);
}int main()
{
init();while(scanf("%d", &n) != EOF){
scanf("%s", s);if(n & 1){
printf("0\n");continue;}solve();}return 0;
}/* 4 () 4 ( 6 () *//* 1 2 2 */