ゆるふわ競プロオンサイト #3 : Yet Another Cake Division

これは勉強になりました。
https://www.hackerrank.com/contests/yfkpo3-1/challenges/yet-another-cake-division

問題

H*Wのグリッドを上下左右に分割する。
各分割領域は凸であり、面積が1マス以上あって、上部の最下段は下部の最上段の上にあり、左部の最右列は右部の最左列の左になければならない。
また、左部は上部の左下になければならず、他同様とする。
分割の仕方は何通りか。

解法

包除原理で解く。
C色以下で塗るケースを列挙しよう。
その際、グリッドの罫線部に着目し、左上角を(0,0)、右下角を(W,H)とする。

• 4色の塗り分け方は、左上から右下と左下から右上に線にそってそれぞれ分割したときの組み合わせに等しいのでComb(H+W,W)^2。
• 以降同様に1・2・3色以下のケースを求め増減させればよい。これらは上の4色に比べると単純な数え上げで計算できる。

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;
}

int H,W;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	// all
	ll ret=comb(H+W,W)*comb(H+W,W)%mo;
	// -1
	FOR(y,H+1) ret-=2*comb(y+W,W)*comb(H-y+W-1,W-1)%mo;
	FOR(x,W+1) ret-=2*comb(x+H,H)*comb(W-x+H-1,H-1)%mo;
	// -2
	ret+=4*comb(H+W,W);
	ret+=(W+1)+(H+1);
	// -3
	ret-=4;
	
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

4色のケースをさっと思い浮かべられないなー。