Codeforces #424 Div1 D. Singer House

終わってみれば非常にシンプル。
http://codeforces.com/contest/830/problem/D

問題

変則的な高さkの完全二分木を考える。
通常の完全二分木に加え、各頂点は直接の親だけでなくその祖先すべてに辺をもつ。

この木について、同じ頂点を２回以上通らないパスは何通りあるか答えよ。

解法

以下を考えよう。求めたいのはf(k,1)である。
f(n,a) := 高さnの変則二分木で、パスがa個あるものの組み合わせ

高さnの木を２つ横に並べ、両者の根の上にさらに頂点を1個配置すれば、高さ(n+1)の木ができる。
さて、左右の高さnの木がそれぞれパス数がa,bの場合を考える。
f(n,a)とf(n,b)からf(n+1,*)への遷移を考えよう。

• 新しい根頂点はパスを構成しない場合: f(n+1,a+b) += f(n,a)*f(n,b)
• 新しい根頂点は単独でパスを構成し、子頂点とはつなげない場合: f(n+1,a+b+1) += f(n,a)*f(n,b)
• 新しい根頂点は既存のパスのいずれか1つとつなげる。先頭と末尾どちらにつなげるか2とおりあるので: f(n+1,a+b) += f(n,a)*f(n,b)*2*(a+b)
• 新しい根頂点は既存のパスのいずれか2つとつなげる。: f(n+1,a+b-1) += f(n,a)*f(n,b)*(a+b)*(a+b-1)

int N;
ll mo=1000000007;

ll dp[405][405];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0][0]=1;
	for(i=1;i<=400;i++) {
		FOR(x,404) FOR(y,404) if(x+y<404) {
			ll pat=dp[i-1][x]*dp[i-1][y]%mo;
			//take 0 and connect 1
			(dp[i][x+y] += pat*(1+2*(x+y)))%=mo;
			//connect 2
			if(x+y>0) (dp[i][x+y-1] += pat*((x+y)*(x+y-1)))%=mo;
			//new
			dp[i][x+y+1] += pat;
			if(dp[i][x+y+1]>=mo) dp[i][x+y+1]-=mo;
		}
	}
	cin>>N;
	cout<<dp[N][1]<<endl;
	
	
}

まとめ

本番O(k^2)のコードでサンプルが通らない…と唸ってしまった。