TopCoder SRM 664 Div1 Medium BearAttacks

本番あと１歩だったけど解けなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13915

問題

0～(N-1)番の各町を頂点とする木を成す無向グラフが与えられる。
各町には１度ずつ攻撃がなされ、i番の町は1/(i+1)の確率で生き残る。
町が破壊されると、同時にその町を端点とする辺も破壊される。

攻撃終了後のグラフにおいて、生き残った町同士の連結成分を考える。
各連結成分の強さは、連結成分を構成する町の数の２乗であり、グラフ全体の強さは各連結成分の和だとする。

攻撃終了後のグラフの強さの期待値Eを求め、E*N!は必ず整数になるので、E*N!の値を答えよ。

解法

まず辺がない場合、各頂点が生き残る確率は1/(i+1)なので、強さの期待値Eにもその分1/(i+1)加算する。

あとは頂点同士が連結することによる強さの増分を考える。
A頂点からなる連結グラフとB頂点からなる連結グラフがある場合、その強さはA^2+B^2である。
しかしこれらを１辺追加して結ぶと、その強さは(A+B)^=A^2+B^2+2*A*Bとなる。
すなわち、辺で頂点同士を結ぶことで、2*A*B分だけ強さが増すことになる。

よって根付き木をDFSし、辺の両端におけるA,Bの期待値を求めて2*A*Bを解に加算していけば良い。
同じ頂点対の影響による増分を多重カウントしないように注意。
(下記コードではdfs中のtot[cur]+=mo-dp[t]で多重カウントを防いでいる。)

const int NUM_=1000005;
ll inv[NUM_+1];

vector<int> E[1010101];
int par[1010101];
ll dp[1010101],tot[1010101];
ll mo=1000000007;

class BearAttacks {
	public:
	int root;
	ll ret;
	
	void dfs(int cur,ll sc) {
		(ret += 2*sc*inv[cur+1])%=mo;
		FORR(t,E[cur]) {
			tot[cur]+=mo-dp[t];
			ll sc2=(sc+tot[cur]+mo)%mo*inv[cur+1]%mo;
			dfs(t,sc2);
		}
	}

	int expectedValue(int N, int R0, int A, int B, int M, int LOW, int HIGH) {
		int i;
		
		inv[1]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		FOR(i,N) E[i].clear();
		
		ll R = R0;
		ll BILLION = 1000000000;
		for(i=1;i<=N-1;i++) {
			R = (A * R + B) % M;
			ll MIN = (1LL*(i-1) * LOW)  / BILLION;
			ll MAX = (1LL*(i-1) * HIGH) / BILLION;
			par[i]= MIN + (R % (MAX-MIN+1));
			E[par[i]].push_back(i);
		}
		ZERO(dp);
		ZERO(tot);
		
		ret=0;
		for(i=N-1;i>=0;i--) {
			tot[i]++;
			tot[i]%=mo;
			dp[i]=tot[i]*inv[i+1]%mo;
			if(i) tot[par[i]] += dp[i];
			
			(ret += inv[i+1])%=mo;
		}
		
		dfs(0,0);
		for(i=1;i<=N;i++) ret = ret*i%mo;
		
		return ret;
	}
}

まとめ

本番2*A*Bを足しこんでいくことには気づいたけど、多重カウントに気づかず時間切れ。