本番あと1歩だったけど解けなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13915
問題
0~(N-1)番の各町を頂点とする木を成す無向グラフが与えられる。
各町には1度ずつ攻撃がなされ、i番の町は1/(i+1)の確率で生き残る。
町が破壊されると、同時にその町を端点とする辺も破壊される。
攻撃終了後のグラフにおいて、生き残った町同士の連結成分を考える。
各連結成分の強さは、連結成分を構成する町の数の2乗であり、グラフ全体の強さは各連結成分の和だとする。
攻撃終了後のグラフの強さの期待値Eを求め、E*N!は必ず整数になるので、E*N!の値を答えよ。
解法
まず辺がない場合、各頂点が生き残る確率は1/(i+1)なので、強さの期待値Eにもその分1/(i+1)加算する。
あとは頂点同士が連結することによる強さの増分を考える。
A頂点からなる連結グラフとB頂点からなる連結グラフがある場合、その強さはA^2+B^2である。
しかしこれらを1辺追加して結ぶと、その強さは(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を足しこんでいくことには気づいたけど、多重カウントに気づかず時間切れ。