SRM402 Div2 1000

問題

ある数列permutationが与えられる．これは1からnまでの数字がn個ランダムに並んでおり，これを昇順に並べたい．そこで，ipermutation[j]であるような(i,j)の組のswapを考える．各状態でswapは等確率で選ばれるとき，与えられた数列を昇順に並べるのに必要なswapの回数の期待値を求める．

考え方

それぞれの数列が何回でそろうかの期待値を計算する．
まず，ある数列について，swapできる回数countを計算する．count==0ならば，すでに昇順にならんでいるので0回でそろう(すでにそろってる)．
count>0ならば，swap後の数列から等確率(1/count)で選ばれるので，この数列の期待値はswap後の数列の分足した，Σ{(swap後の数列の期待値+この数列からのswap1回)*(1/count)}となる．

あとは，各数列の昇順に並べるまでかかる期待されるswap回数(期待値)が上の方法でもとめられるので，各数列の期待値をメモ化すればいい．

反省

vectorをmapの要素とするときは，map.count(v)でその配列があるかどうかをチェックできる．
期待値周りがよくわかってない．