Codeforces 785 D. Anton and School

题目链接：http://codeforces.com/contest/785/problem/D

我们可以枚举分界点，易知分界点左边和右边分别有多少个左括号和右括号，为了不计算重复我们强制要求选择分界点左边的那一个左括号(也就是说如果枚举的这个分界点的左边这个位置没有左括号就强制这个位置不产生贡献)。

对于一个分界点我们记它左边有$le[x]$个左括号，右边有$ri[x]$个右括号。

${Ans=sum_{x=1}^{n-1} sum _{i=1}^{min(le[x]-1,ri[x]])}C(le[x]-1,i)*C(r[x],i)}$

${=sum_{x=1}^{n-1} C(le[x]-1+ri[x],ri[x])}$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<cstring>
 8 using namespace std;
 9 #define maxn 1000010
10 #define llg long long 
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 #define md 1000000007
13 llg n,m,le[maxn],ri[maxn],inv[maxn],fac[maxn];
14 
15 char c[maxn];
16 
17 llg ksm(llg a,llg b)
18 {
19     llg ans=1;
20     while (b)
21     {
22         if (b&1) ans*=a,ans%=md;
23         a*=a,a%=md;
24         b/=2;
25     }
26     return ans;
27 }
28 
29 llg C(llg N,llg M)
30 {
31     if (M==0) return 1;
32     return fac[N]*inv[M]%md*inv[N-M]%md;  
33 }
34 
35 int main()
36 {
37     yyj("D");
38     scanf("%s",c+1);
39     n=strlen(c+1);
40     llg p=0;
41     for (llg i=1;i<=n;i++)
42     {
43         if (c[i]=='(') p++;
44         le[i+1]=p;
45     }
46     p=0;
47     for (llg i=n;i>=1;i--)
48     {
49         if (c[i]==')') p++;
50         ri[i]=p;
51     }
52     fac[0]=1;
53     llg ans=0;
54     for (llg i=1;i<=n*2+10;i++) 
55         fac[i]=fac[i-1]*i%md,inv[i]=ksm(fac[i],md-2);
56 //    fac[0]=0;
57     for (llg i=2;i<=n;i++) 
58         if (le[i] && ri[i] && c[i-1]=='(') 
59         ans+=C(le[i]+ri[i]-1,ri[i]-1),ans%=md;
60     cout<<ans;
61     return 0;
62 }