Codeforces #224 Div2. E. Ksenia and Combinatorics

コード量はそこまで多くないが、ややこしい問題。
いまだ正答数も少なめ。
http://codeforces.com/contest/382/problem/E

問題

数N・Kが与えられる。
1～Nの番号が振られた点からなり、1番の点を根とする二分木において、点の最大マッチング数がKとなるような根つき木グラフの組み合わせを列挙せよ。

解法

subtreeの状態としてdp[点の数][マッチング数][根を親の点とマッチングさせたいか否か]を取り、より小さな木から組み合わせ数をDPで求めていけばよい。

dp[x][y][0]及びdp[x][y][1]を求めるため、より小さなx,yの値から以下のように計算する。

• 根が２つの子を持つ場合、２つのsubtreeの点の数L,Rを、それぞれ1～(x-2)、和がx-1となるように総当たりする。
  • まず根を除く(x-1)点の分け方として、２つの子の番号を個選択し、かつそれ以下の点をどう２つの子に振り分けるか通りある。
  • さらに、２つのsubtreeのマッチング数を総当たりする。
    • ２つのsubtreeの根がともにマッチング済みの場合、現在の根は親とマッチングを取りたい(コード中(dpdp[x][y][1] += pat*dpdp[l][lk][0]%mo*dpdp[r][rk][0];))
    • ２つのsubtreeの根のどちらか片方でもマッチングしてない根がある場合、現在の根とその根のマッチングをとり、マッチング数を1追加する(コード中(dpdp[x][y][0] += ～～ の３行)
• 次に、根が１つの子をもつ場合を考える。
  • まずsubtreeの根の頂点の番号を(x-1)個から選択する。
    • subtreeの根がマッチング済みの場合、現在の根は親とマッチングを取りたい(コード中(if(y>0) dpdp[x][y][0] += (x-1)*dpdp[x-1][y-1][1]))
    • subtreeの根かマッチングしてないある場合、現在の根とその根のマッチングをとり、マッチング数を1追加する(コード中(dpdp[x][y][1] += (x-1)*dpdp[x-1][y][0];))

最終的な答えは、全体の根がさらにマッチングを求めていても求めていなくてもマッチング数がKに到達すればよいので、dp[N][K][0]+dp[N][K][1]になる。

ll mo=1000000007;
int N,K;
ll dpdp[51][51][2];

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	
	dpdp[1][0][1]=1;
	
	for(x=2;x<=N;x++) FOR(y,K+1) { // x=num y=match
		// bintree
		for(l=1;l<=x-2;l++) {
			int r=x-1-l;
			ll pat=comb(x-1,2)*comb(x-3,l-1)%mo;
			
			for(int lk=0;lk<=y;lk++) {
				int rk=y-lk;
				dpdp[x][y][1] += pat*dpdp[l][lk][0]%mo*dpdp[r][rk][0];
				dpdp[x][y][1] %= mo;
			}
			
			for(int lk=0;lk<=y-1;lk++) {
				int rk=y-1-lk;
				dpdp[x][y][0] += pat*dpdp[l][lk][1]%mo*dpdp[r][rk][0];
				dpdp[x][y][0] += pat*dpdp[l][lk][0]%mo*dpdp[r][rk][1];
				dpdp[x][y][0] += pat*dpdp[l][lk][1]%mo*dpdp[r][rk][1];
				dpdp[x][y][0] %= mo;
			}
		}
		
		// monotree
		if(y>0) dpdp[x][y][0] += (x-1)*dpdp[x-1][y-1][1];
		dpdp[x][y][1] += (x-1)*dpdp[x-1][y][0];
		dpdp[x][y][0] %= mo;
		dpdp[x][y][1] %= mo;
	}
	
	cout << (dpdp[N][K][0]+dpdp[N][K][1])%mo << endl;
}

まとめ

最初親から順にマッチングを確定していったら、点が変に余って最大マッチングが取れなかった。
二分木の最大マッチングは葉から確定させればいいのか。