問題概要
次の条件を全て満たす、長さ $N$ の文字列をRSBS文字列という。与えられる文字列の subsequence であって、RSBS文字列であるものの個数を $10^{9}+7$ で割った余りを求めよ。
- 長さ $N$ が偶数である
- 前半 $\frac{N}{2}$ 個は全て '(' である
- 後半 $\frac{N}{2}$ 個は全て ')' である
制約
- $1 \leq N \leq 200000$
解法
数え上げの方針自体は容易で、RSBS文字列に用いられる一番右側の '(' の位置を固定すると重複無く数え上げることができる。
具体的には固定したindex自身及び左側に存在する '(' の個数を $A$ 個、右側に存在する ')' の個数を $B$ 個とすると、
$$\displaystyle \sum _ {i=1}^{\min (A, B)}({ _ {A-1}C _ {i-1}} \cdot { _ BC _ i}) $$
を計算すれば良い。これを高速に求めたい。
シグマの中身を次のように変形すると、
$$ { _ {A-1}C _ {i-1}} \cdot { _ BC _ i} = { _ {A-1}C _ {A-i}} \cdot { _ BC _ i} $$
$(A - i) + i = A$ が不変量となる。結局総和を取ることによって何をしているかというと、$A-1$ 個の集合及び $B$ 個の集合から合わせて $A$ 個を選び出す通り数を求めている。これは $A-1$ 個の集合から取り出す個数を固定し、全て足し合わせることを考えれば分かる。
ところで $A-1$ 個の集合及び $B$ 個の集合から合わせて $A$ 個を選び出す通り数は、$_ {A+B-1}C _ {A}$ に等しい。つまり、
$$\displaystyle \sum _ {i=1}^{\min (A, B)}({ _ {A-1}C _ {i-1}} \cdot { _ BC _ i}) = _ {A+B-1}C _ {A}$$
が成立する。後はこれを利用すれば良い。
実装
#include <bits/stdc++.h> using namespace std; typedef long long int ll; constexpr ll mod=1e9+7; struct perm{ // 二項係数ライブラリ(省略) }; perm p(1<<21); int main(){ string s; cin >> s; int n=s.size(); ll res=0; int a=0,b=0; for(char c:s)if(c==')')b++; for(int i=0;i<n;i++){ if(s[i]=='('){ a++; res+=p.comb(a+b-1,a); if(res>=mod)res-=mod; } else b--; } printf("%lld\n",res); }
おまけ
これを知っていれば一発。同様の方針で示すこともできる。
