CF 785 D - Anton and School - 2
問題
問題概要
(
と)
のみで構成される文字列について、次のような長さの文字列をregular simple bracket sequences(RSBS)
と呼ぶことにする:
- 空文字列ではない()
- は偶数で、前半の文字は全て
(
、後半の文字は全て)
例えば((()))
はRSBSで、())
や(()())
はRSBSではない。
今、(
と)
のみで構成される文字列が与えられる。からいくつかの文字を削除してRSBSを作成したいと思う時、その方法は何通りあるか、で割った余りを答えよ。
アイデア
要するに、の部分文字列の中でRSBSの個数を求めたい。まず、自分で考えたこととしてはを先頭から走査していってその時点で左にある(
の合計(個とする)と右にある)
の合計(個とする)がわかっていれば、現在注目している箇所の(
を必ず採用すると仮定してで組み合わせの総数を列挙できるなーとは思った。けれど、それを全ての(
に対してやるのは間に合わない。
実は、1箇所の(
に注目して、それより左にある(
の個数が個でそれより右にある)
の個数が個の時のRSBSの構成方法の場合の数はもっと簡単に計算できる。
シンプルな場合として、前半文字が(
で後半文字が)
のような文字列からRSBSを構成することを考えると、この場合は通りになる。なぜこうなるかを、個の1と個0を並べる順列に対応付けて考える。
以下に例を示す:
s: ((()))) select: ( ( )) convert: 0100110
元の文字列がであるときに、このように部分文字列を構成すると、01はこのように対応させる。これは具体的に何をやっているかというと、部分文字列として採用された(
に0、されない(
に1、採用された)
に1、されない)
に0を付与している。この方法によって、0は個、1は個になる。
採用された(
が個とすると、採用された)
も個。つまり採用されない)
は個。ということで、0は合計で個になる。前から順番に括弧を対応させていくことで一対一にこの文字列が定まるというわけである。
実際に走査していく時は、一番右にある(
は必ず採用する仮定があるので、01の対応で言うと0が1つ減ることになる。よって、通りになる。
あとは、はじめに)
の数を数えておいて、操作しながら減らしていき、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; }