kmjp's blog

競技プログラミング参加記です

Codeforces #404 Div2 D. Anton and School - 2

Codeforces

手間取ったけどまぁ解けたのでよかった。
http://codeforces.com/contest/785/problem/D

問題

括弧だけで構成された文字列Sがある。

このSの空でない(非連続でもよい)部分文字列のうち、前半半分が開き括弧、後半半分が同数の閉じ括弧であるようなもの答えよ。
なお、得られる部分文字列が等しくても、選んだ位置が異なるならそれらは別物をみなす。

解法

開き括弧のうち最も内側となるものを総当たりし、対応する文字列を数え上げよう。
今S[i]='('であるとし、S[0..i]にある開き括弧の数をL、S[(i+1)..(|S|-1)]にある閉じ括弧の数をRとする。

この時、条件を満たす文字列の数は、L個中一番内側の開き括弧と、それに加えていくつか残す開き括弧を選択し、R個から同数の残す文字を選択するので \displaystyle \sum_{i=1}^{L} {}_{L-1} C_{i-1} \times {}_R C_iとなる。
この計算を最終的には開き括弧の回数だけ行わないといけないので、全体で間に合うようO(1)で済ませることを考える。

少し単純化して、 \displaystyle \sum_{i=0}^{P} {}_P C_i \times {}_Q C_iの形の式を高速に解くことを考える。
{}_Q C_i = {}_Q C_{Q-i}より、 \displaystyle \sum_{i=0}^{P} {}_P C_i \times {}_Q C_i = \sum_{i=1}^{P} {}_P C_i \times {}_Q C_{Q-i}となる。
ここで、この式は「P個のうちi個選び、Q個のうち(Q-i)個選ぶということを各iについて行う」ということを意味するが、これは結局「(P+Q)個からQ個選ぶ」というのと同じである。
よって \displaystyle \sum_{i=0}^{P} {}_P C_i \times {}_Q C_i = {}_{P+Q} C_Q とシンプルな形になり、前処理で階乗や階乗の逆数を列挙しておくとO(1)で計算できる。

元の式も-1の分少し変化があるが、 \displaystyle \sum_{i=1}^{L} {}_{L-1} C_{i-1} \times {}_R C_i = {}_{L+R-1} C_{R-1}と似た形に列挙できる。

ll mo=1000000007;
ll combi(ll N_, ll C_) {
	const int NUM_=500001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

string S;
int N;
int L[202020],R[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N) L[i+1]=L[i]+(S[i]=='(');
	for(i=N-1;i>=0;i--) R[i]=R[i+1]+(S[i]==')');
	
	ll ret=0;
	FOR(i,N) if(S[i]=='(') {
		int left=L[i+1]-1;
		int right=R[i+1];
		
		ret += combi(left+right,left+1);
	}
	cout<<ret%mo<<endl;
	
}

まとめ

CombinationのSumについて、実験したのちそのままあてずっぽうでやってしまった。
落ち着いて考えればこの式変形は簡単なのね。