EEIC Programming Contest #0 : D. Brackets Restoring

これはライブラリ化していたのですんなりだった。
https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/brackets-restoring

問題

Nに対し2N文字以下の括弧列Sが与えられる。
Sの後ろに(2N-|S|)文字の括弧列を加え、全体の整合性が取れた括弧列を作りたい。
加える括弧列は何通りか。

解法

まずSの時点で閉じ括弧が超過している場合は不可。
Sの時点で開き括弧がA個多いとする。
そうすると、残り開き括弧Xと閉じ括弧の数Yは以下の2式から確定する。

• X-Y=A
• X+Y=2N-|S|

あとはX個の開き括弧とY個の閉じ括弧が、閉じ括弧が(A+1)個以上多く先行しないように並べる問題となる。
これはカタラン数の変形でCombinationを使い高速に求められる。
この開き括弧と閉じ括弧の数が違うカタラン数の変形は、AGC021Eの解説で言及されている。
https://img.atcoder.jp/agc021/editorial.pdf

int N,K;
string S;
ll mo=1000000007;

ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	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;
}

ll catalan_arrange(int X,int Y,int T=1) {
	return (comb(X+Y,Y)-comb(X+Y,Y-T)+mo)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	int cur=0;
	FOR(i,K) {
		if(S[i]=='(') cur++;
		if(S[i]==')') cur--;
		if(cur<0) return _P("0\n");
	}
	
	int op=(2*N-K-cur)/2;
	int cl=2*N-K-op;
	if(op<0 || cl<0) return _P("0\n");
	cout<<catalan_arrange(op,cl,cl-op+1)<<endl;
	
	
}

まとめ

カタラン数の変形版を持っててよかった。