終わってみれば非常にシンプル。
http://codeforces.com/contest/830/problem/D
問題
変則的な高さkの完全二分木を考える。
通常の完全二分木に加え、各頂点は直接の親だけでなくその祖先すべてに辺をもつ。
この木について、同じ頂点を2回以上通らないパスは何通りあるか答えよ。
解法
以下を考えよう。求めたいのはf(k,1)である。
f(n,a) := 高さnの変則二分木で、パスがa個あるものの組み合わせ
高さnの木を2つ横に並べ、両者の根の上にさらに頂点を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)のコードでサンプルが通らない…と唸ってしまった。