TopCoder Open 2014 Round1B Hard EagleInZoo

問題

根付き木が与えられる。
この木に対して次の操作をK回行う。

K番目の操作を行ったとき、K番目の鳥がどこかの頂点に入れる確率を求めよ。

操作：
根に鳥が来る。
鳥が今いる頂点に、他の鳥がまだいなければその頂点に入って終了。
そうでない場合、子を等確率で一つ選び、そこに移動して同様のことを行う。
子がなかった場合、どこにも入らずに終了。

制約条件

木の頂点≦51
K≦100

方針

メモ化再帰。
rec(c, num)を、頂点cを根とする部分木にnum羽の鳥が来たとき、
最後の一羽がどこかに止まれる確率とする。

num = 1だったら根に止まればよいので終了。
それ以外の場合は、最後の一羽がどこに移動するかで場合分け。
最後の一羽が行く頂点にx羽が行くとすると、
最後の一羽が止まれる確率は
rec(child, x)を含む式になって、再帰で計算できる。

最後の一羽以外の鳥が、childの頂点にx羽行く確率は、
全ての子の頂点が等確率で選ばれるので、確率pで表が出るコインをm枚投げて、
x回表が出る確率として求めればよい。

ソースコード

vector<vi> e;
long double dp[51][110];
long double C[110][110];

long double rec(int c, int num){
	long double &res = dp[c][num];
	
	if(res >= 0) return res;
	if(num == 1) return res = 1;
	
	res = 0;
	rep(i, e[c].size()) rep(j, num - 1){
		
		res += C[num - 2][j] * pow(1.0l / e[c].size(), j)
		* pow(1 - 1.0l / e[c].size(), num - 2 - j)
		/ e[c].size()
		* rec(e[c][i], j + 1);
	}
	return res;
}

class EagleInZoo {
	public:
	double calc(vector <int> parent, int K) {
		
		int n = parent.size() + 1;
		e.clear();
		e.resize(n);
		memset(dp, -1, sizeof(dp));
		rep(i, n - 1) e[parent[i]].pb(i + 1);
		
		rep(i, 110) rep(j, i+1) C[i][j] = j==0||j==i ? 1 : C[i-1][j] + C[i-1][j-1];
		
		return (double)rec(0, K);
	}
};