Codeforces ECR #57 F. Inversion Expectation
問題概要
一部が -1 である [1,N] のpermが与えられる.
各-1に等確率で残りの数が入る時,転倒数の期待値を求めよ.
解法
A = もともとある数, B = -1の場所に入る数 とする.
A-A, A-B, B-B の期待値を足せば良い.
A-A はBITを使って数え上げる.
B-B は b1, b2 in B が転倒している確率は 1/2なので,
これを全てのペアについて足し, |B| (|B|-1) /4.
以下でA-Bの期待値を考える.
x in B をどの-1に挿入する確率も 1/|B| なので,
xが片方になる転倒ペアを数え上げてこの確率をかける.
これは i in A に対して
left( i ) := ( i の左にある-1の数), rightも同様に定義すると,
sum{ y in A, y < x} left(y) + sum{ y in A, y < x } right(y) となる.
これは累積和で求められる.
