yukicoder : No.1662 (ox) Alternative

こういう式変形苦手。
https://yukicoder.me/problems/no/1662

問題

(,),o,xがそれぞれA,B,C,D個あり、それらを並べ替えて作れる文字列Sを考える。
o→()、x→)(と置き換えたとき、Sが正当な括弧列であるような並びは何通りか。

解法

まず自明なこととして

• oはどこに入れても良い
• Sから(と)を取り出した部分列は、正当な括弧列でないといけない。よってA=B。
• xは、1個以上の(,)に囲まれたところに挿入可能

oの対処は、o以外のA+B+D要素の並びが決まった後に任意の場所に挿入すればよい。
よって以後(,),xのことだけ考える。

(,)だけ並べたとき、prefixにおいて(と)の数が釣り合う場所が、先頭と末尾以外にk箇所あるケースをf(A,k)とする。
すると、A+B=2A個の文字の間のうち、そのk箇所を除く(2A-1-k)箇所にxを挿入するので、解は
である。

f(A,k)はCatalan数の応用でと書ける。
これで元の式の値は計算できるものの、まだsumの処理が重い。
ただ、Editorialの通り式変形するととできる。

int T;
int A,B,C,D;
const int NUM_=500001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}
ll catalan(int n) {
	return fact[2*n]*factr[n]%mo*factr[n+1]%mo;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>C>>D;
		if(A!=B) {
			cout<<0<<endl;
			continue;
		}
		if(A==0) {
			if(D) {
				cout<<0<<endl;
			}
			else {
				cout<<1<<endl;
			}
			continue;
		}
		ll ret=0;
		ret=comb(A+D-1,A-1)*comb(2*A+D,A-1)%mo*modpow(A)%mo;
		
		
		ret=ret*comb(A+B+C+D,C)%mo;
		cout<<ret<<endl;
	}
}

まとめ

この式変形できる気しないな…。
ただ、f(A,x)の計算方法は覚えておきたい。