【HDU 5184】 Brackets （卡特兰数）

Brackets

Problem Description

We give the following inductive definition of a “regular brackets” sequence:
● the empty sequence is a regular brackets sequence,
● if s is a regular brackets sequence, then (s) are regular brackets sequences, and
● if a and b are regular brackets sequences, then ab is a regular brackets sequence.
● no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:
(), (()), ()(), ()(())
while the following character sequences are not:
(, ), )(, ((), ((()

Now we want to construct a regular brackets sequence of length

Input

Multi test cases (about

Output

For each case，output answer %

Sample Input

4

()

4

(

6

()

【题意】

　　括号匹配（<=10^6），给出已将匹配好的前若干个的括号，让你把剩下的匹配完，问方案数%10^9+7,多组数据<=1000

【分析】

　　跟上一题类似。先判断他给的括号是否匹配。然后假设左括号比右括号多了l个，就是要求任意前缀和>=l的方案数。也用1与-1互换的方法推

　　上一个厉害的证明：

　　转自：http://blog.csdn.net/i_fuqiang/article/details/8501141

　　我的理解在上一篇博写了~

代码如下：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 using namespace std;
 9 #define Maxn 1000010
10 #define Mod 1000000007
11 #define LL long long
12 
13 char s[Maxn];
14 int p[Maxn];
15 
16 void init()
17 {
18     p[0]=1;
19     for(int i=1;i<=Maxn-10;i++)
20     {
21         LL x=(LL)p[i-1],y=(LL)i,z;
22         z=(x*y)%Mod;
23         p[i]=(int)z;
24     }
25 }
26 
27 LL qpow(int x,int b)
28 {
29     if(x==0) return 1;
30     LL xx=x,ans=1;
31     while(b)
32     {
33         if(b&1) ans=(ans*xx)%Mod;
34         xx=(xx*xx)%Mod;
35         b>>=1;
36     }
37     return ans;
38 }
39 
40 int get_c(int n,int m)
41 {
42     LL ans=p[m];
43     ans=(ans*qpow(p[n],Mod-2))%Mod;
44     ans=(ans*qpow(p[m-n],Mod-2))%Mod;
45     return (int)ans;
46 }
47 
48 int main()
49 {
50     init();
51     int n;
52     while(scanf("%d",&n)!=EOF)
53     {
54         int m,sl=0;
55         scanf("%s",s+1);
56         int l=strlen(s+1),now=0;
57         bool ok=1;
58         for(int i=1;i<=l;i++)
59         {
60             if(s[i]=='(') now++,sl++;
61             else now--;
62             if(now<0) ok=0;
63         }
64         if(n%2!=0||l>n||!ok||sl*2>n||(l-sl)*2>n) {printf("0
");continue;}
65         m=n/2-sl;
66         if(sl==n/2||l==n) {printf("1
");continue;}
67         printf("%d
",(get_c(m,2*m+now)+Mod-get_c(m-1,2*m+now))%Mod);
68     }
69     return 0;
70 }

[HDU 5184]

2016-09-20 19:53:38