Codeforces 785D

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

题意：有一行包含 “（”与“）”的字符串，若删去其中几个“（”和“）”得到形如“（）”、“（（））”的字符串，这种字符串叫做RSBS串。

每一种不同的删法得到一个不同的RSBS串，问有几个不同的RSBS串

思路：（官方解法）从左往右遍历每一个括号，对于每一个“（”，假设其左边（包括它）有x个“（”，右边有y个“）”，则方案数有

用范德蒙行列式把上式化成：即可

AC代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<string>
 5 using namespace std;
 6 const int mod=1e9+7;
 7 const int MAXN=4e5+10;
 8 int pre1[MAXN],pre2[MAXN];
 9 long long fac[MAXN],inv[MAXN];
10 long long Pow(long long a, long long p){
11     a%=mod;
12     long long ans=1;
13     while(p){
14         if(p&1) ans=ans*a%mod;
15         a=a*a%mod;
16         p>>=1;
17     }
18     return ans;
19 } 
20 void init(){
21     fac[0]=1;
22     inv[0]=1;
23     for(int i=1;i<MAXN;i++){
24         fac[i]=fac[i-1]*i%mod;    
25         inv[i]=Pow(fac[i], mod-2);
26     }
27     return;
28     
29 }
30 long long cal(int m, int n){
31     if(m<n||m<0) return 0;
32     long long res=fac[m]*inv[m-n]%mod*inv[n]%mod;
33     //cout<<res<<endl;
34     return res;
35 }
36 int main()
37 {
38     string str;
39     cin>>str;
40     int len=str.length();
41     int l=0,r=0;
42     init();
43     memset(pre1, 0, sizeof(pre1));
44     memset(pre2, 0, sizeof(pre2));
45     for(int i=0;i<len;i++){
46         if(str[i]==')') r++;
47     }
48     int p1, p2;
49     long long ans=0;
50     for(int i=0;i<len;i++){
51         if(str[i]==')') r--;
52         else
53         {
54             ans=(ans+cal(l+r, l+1))%mod;
55             l++;
56         }
57         cout<<ans<<endl;
58     }
59     printf("%I64d
", ans);
60 }

∑i=0min(x.y−1)CxiCy−1i