裏紙

ほぼ競プロ、たまに日記

CF 785 D - Anton and School - 2

問題

Problem - D - Codeforces

問題概要

()のみで構成される文字列について、次のような長さnの文字列をregular simple bracket sequences(RSBS)と呼ぶことにする:

  • 空文字列ではない(n \neq 0)
  • nは偶数で、前半の\frac{n}{2}文字は全て(、後半の\frac{n}{2}文字は全て)

例えば((()))はRSBSで、())(()())はRSBSではない。

今、()のみで構成される文字列sが与えられる。sからいくつかの文字を削除してRSBSを作成したいと思う時、その方法は何通りあるか、10^9+7で割った余りを答えよ。

  •  |s| \le 200000

イデア

要するに、sの部分文字列の中でRSBSの個数を求めたい。まず、自分で考えたこととしてはsを先頭から走査していってその時点で左にある(の合計(x個とする)と右にある)の合計(y個とする)がわかっていれば、現在注目している箇所の(を必ず採用すると仮定してO(|s|)で組み合わせの総数を列挙できるなーとは思った。けれど、それを全ての(に対してやるのは間に合わない。

実は、1箇所の(に注目して、それより左にある(の個数がx個でそれより右にある)の個数がy個の時のRSBSの構成方法の場合の数はもっと簡単に計算できる。

シンプルな場合として、前半x文字が(で後半y文字が)のような文字列からRSBSを構成することを考えると、この場合は{} _{x+y} C_x 通りになる。なぜこうなるかを、x個の1とy個0を並べる順列に対応付けて考える。

以下に例を示す:

s:       ((())))
select:  ( ( )) 
convert: 0100110

元の文字列がsであるときに、このように部分文字列を構成すると、01はこのように対応させる。これは具体的に何をやっているかというと、部分文字列として採用された(に0、されない(に1、採用された)に1、されない)に0を付与している。この方法によって、0はy個、1はx個になる。

採用された(z個とすると、採用された)z個。つまり採用されない)y-z個。ということで、0は合計でz + (y-z) = y個になる。前から順番に括弧を対応させていくことで一対一にこの文字列が定まるというわけである。

実際に走査していく時は、一番右にある(は必ず採用する仮定があるので、01の対応で言うと0が1つ減ることになる。よって、{} _{x+y-1} C_x 通りになる。

あとは、はじめに)の数を数えておいて、操作しながら減らしていき、combinationを計算すれば良い。combinationは階乗を事前に計算して、繰り返し二乗法を利用すれば逆元も計算できる。

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const ll mod = 1e9+7;
const int N=202020;

ll fact[N];

inline ll mod_pow(ll x, ll n)
{
    ll pw[32];
    pw[0]=x;
    for(int i=1; i<32; ++i) pw[i]=(pw[i-1]*pw[i-1])%mod;

    ll ret=1;
    rep(i,32)if(n>>i&1) (ret*=pw[i])%=mod;
    return ret;
}

inline ll mod_inv(ll x)
{
    return mod_pow(x,mod-2);
}

inline ll comb(int n, int r)
{
    ll ret = fact[n];
    (ret*=mod_inv(fact[r]))%=mod;
    (ret*=mod_inv(fact[n-r]))%=mod;
    return ret;
}

int main()
{
    fact[0]=1;
    for(int i=1; i<N; ++i) fact[i]=(fact[i-1]*i)%mod;

    string s;
    cin >>s;
    int S = s.size();

    int lb=0,rb=0;
    rep(i,S) rb+=(s[i]==')');

    ll ans=0;

    rep(i,S)
    {
        if(s[i]==')') --rb;
        else
        {
            ++lb;
            (ans+=comb(lb+rb-1,lb))%=mod;
        }
    }

    cout << ans << endl;
    return 0;
}