Codeforces Round #FF D. DZY Loves Games
http://codeforces.com/contest/446/problem/D
概要
N頂点M辺の無向連結グラフ(多重辺もたまにある)があり、ある頂点にいるときはつながっている辺を等しい確率で選んでその先に進む。
頂点にはtrapがあるかどうかが決まっている。
初め頂点1にいる。頂点1にはtrapはなく、頂点Nにはtrapがある。
trapのある頂点に進むと体力が1減る。体力が2の状態で頂点Nにたどり着く確率を求めよ。初めの体力はk
解法
ガウスの消去法+行列累乗
O(N^3+a^3logN) (aはtrap付きの頂点の数)
頂点iからどこかのtrap付き頂点にたどり着くまでのステップを考えると、
j(trapつき)へたどり着く確率P(i,j)は
P(i,j)=ΣP(隣接する頂点,j)/degree[i]
trap付き頂点については、
P(j,j)=1
P(k,j)=0 (j!=k , kにトラップがある)
としておく。
ここで、jがどの頂点でも、trap付きの頂点の式の定数項が変わるだけなので、
trap付き頂点の式の定数項をあたかも変数のように持っておき、その変数に対する係数をもつ。
その情報を含んだn*(2*n)行列でgauss-jordanする。
実際に値を求めるときはjに応じてこの変数を決め、係数を掛ける。
iからtrapのある頂点jに進むとき、
iがtrap付きなら、iの隣接する点たちからjまで進む確率の総和を次数で割る。
iがtrap無しなら、ふつうに。
あとは行列累乗をするだけ。k-1回目のtrapのvisitでNにたどり着けばいい。
