CF785D题解

· · 题解

题面

首先，我们可以预处理出每一位前面的左括号个数以及后面的右括号个数，记为 l_i 和 r_i。

那么，我们枚举选的第一个右括号的位置 i，即枚举所有 s_i=')' 的 i，然后再枚举左右括号的个数 k，此时的方案数为 \sum\limits_{k=1}^{r_i}C_{l_i}^k\times C_{r_i-1}^{k-1}（实际上上界应该是 \min(l_i,r_i)，但是当 m>n 时，C_n^m=0，所以补上几项也无所谓）。

看着上面的式子，我们进行一些改造：

\begin{array}{c} &\sum\limits_{k=1}^{r_i}C_{l_i}^k\times C_{r_i-1}^{k-1}\\ =&\sum\limits_{k=1}^{r_i}C_{l_i}^k\times C_{r_i-1}^{r_i-k}\\ =&C_{l_i+r_i-1}^{r_i} \end{array}

其中最后一步由范德蒙德恒等式得出。

范德蒙德恒等式

\sum\limits_{i=0}^{n}C_n^i\times C_{m}^{r-i}=C_{n+m}^r

证明，假设我们要在 n+m 个球中选出 r 个，那么我们可以前 n 个球选 i 个，后 m 个球选 r-i 个，然后根据加乘原理将方案数算出，即是上式。

代码：

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  const int mod=1e9+7;
  int m,n,x,y,ans,num[40],c[5000005],inc[5000005],l[2000005],r[2000005];
  char s[2000005];
  int fpow(int a,int b){
      if(b<0)return 1;
      int res=1;
      while(b){
          if(b&1)res=res*a%mod;
          a=a*a%mod;
          b>>=1;
      }
      return res;
  }
  inline int C(int n,int m){
      if(m>n)return 0;
      return c[n]*inc[m]%mod*inc[n-m]%mod;
  }
  signed main()
  {
      c[0]=c[1]=1;
      for(int i=2;i<=5000000;i++)c[i]=c[i-1]*i%mod;
      inc[5000000]=fpow(c[5000000],mod-2);
      for(int i=5000000-1;i>=0;i--)inc[i]=inc[i+1]*(i+1)%mod;//初始化阶乘以及逆元
      scanf("%s",s+1);
      n=strlen(s+1);
      for(int i=1;i<=n;i++){
          if(s[i]=='(')l[i]=1;
          else r[i]=1;
      }
      for(int i=1;i<=n;i++)l[i]+=l[i-1];
      for(int i=n;i>=1;i--)r[i]+=r[i+1];//分别计算前后缀和
      for(int i=1;i<=n;i++){
          if(s[i]==')'){
              ans=(ans+C(l[i]+r[i]-1,r[i]))%mod;//累加，原因见上
          }
      }
      printf("%lld",ans);
      return 0;
  }