CFR 785 D. Anton and School - 2 ( Math )

Problem - D - Codeforces

題意：
給一個亂的括弧序列，求有幾個不同 ( 任一元素來自原本序列的不同下標 ) 的子序列，是個正確的括弧匹配序列，且前半是 '('，後半是 ')'。

資料規模：
The only line of the input contains a string s — the bracket sequence given in Anton's homework. The string consists only of characters "(" and ")" (without quotes). It's guaranteed that the string is not empty and its length doesn't exceed 200 000.

解法：
一開始想錯成分治，而分治會爛在分治點左邊有某一定數量的 ')'，右邊也有某一定數量的 ')'，這種匹配情況。
考慮用數式表示所求：



盯久一點就會發現其實：

時間 / 空間複雜度：
O( | S | )

#include <bits/stdc++.h>
using namespace std;

const int MOD = ( int ) 1e9 + 7;
const int MAXLEN = ( int ) 2e5;

string seq;
int l_pfx[ MAXLEN + 1 ];
int r_pfx[ MAXLEN + 1 ];

int fact[ MAXLEN ];
int inv_fact[ MAXLEN ];

int int_pow( int v, int p ){
  int res = not ( v == 0 and p > 0 );
  while( p ){
    if( p & 1 ) res = 1LL * res * v % MOD;
    p >>= 1;
    v = 1LL * v * v % MOD;
  }
  return res;
}

int mod_inv( int v ){
  return int_pow( v, MOD - 2 );
}

int C( int n, int r ){
  return 1LL * fact[ n ] * inv_fact[ n - r ] % MOD * inv_fact[ r ] % MOD;
}

signed main(){
  {
    for( int i = fact[ 0 ] = inv_fact[ 0 ] = 1; i < MAXLEN; ++i ){
      fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD;
      inv_fact[ i ] = mod_inv( fact[ i ] );
    }
  }
  ios::sync_with_stdio( 0 );
  cin >> seq;
  {
    for( int i = 0; i < seq.size(); ++i ){
      l_pfx[ i + 1 ] = l_pfx[ i ] + ( seq[ i ] == '(' );
      r_pfx[ i + 1 ] = r_pfx[ i ] + ( seq[ i ] == ')' );
    }
  }
  int ans = 0;
  for( int i = 0; i < seq.size(); ++i ){
    if( seq[ i ] == '(' ){
      int ll = l_pfx[ i ];
      int rr = r_pfx[ seq.size() ] - r_pfx[ i + 1 ];
      ( ans += C( ll + rr, rr - 1 ) ) %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}