原题链接：

 

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

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

 

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

 

 

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

 

 

 

AC代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          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
         
          >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
         
        
       
      
     

 

 

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