https://codeforces.com/contest/1096/problem/F
1から$N$までの順列のうち、いくつかを-1に置き換えた数列が与えられる。もとの順列として考えられるものが当確率で現れるとき、転倒数の期待値を求めよ。
期待値の線形性から、求める期待値は「確定している要素同士の転倒数の期待値＋確定している要素と確定していない要素の転倒数の期待値＋確定していない要素同士の転倒数の期待値」と求められる。
確定している要素同士の転倒数の期待値は、そのまま確定している要素同士の転倒数を求めればよい。
確定している要素と確定していない要素の転倒数の期待値は、同じく期待値の線形性より、各確定済要素A[i]の「A[i]より前にあるA[i]より大きい要素の数の期待値＋A[i]より後ろにあるA[i]より小さい要素の数の期待値」の和で求められる。さらに、A[i]より前に存在するそれぞれの-1にA[i]より大きい数字が入る確率は「与えられた数列で確定されていないA[i]より大きい数字の数 / 与えられた数列で確定されていない数字の数」で求められて、A[i]より前に存在するA[i]より大きい数字の数の期待値は、これらをA[i]より前にある-1の数だけ足し合わせたものである。後ろについても同様であって、これで確定している要素と確定していない要素の転倒数の期待値がわかる。
確定していない要素同士の転倒数の期待値は、確定していない要素の数を$M$として $$\frac{M(M-1)}{4}$$ で与えられる。これは、各ペアについて転倒している確率が1/2であって、ペアの数が$\frac{M(M-1)}{2}$個あることによる。
答えを$P・Q^{-1}$で求める問題と初めて向き合ったので戸惑ってしまった。実際には、有理数はmod上である整数と合同であるので、整数同士のmodのように四則演算をしてよい。期待値の線形性についてはもう少し慣れたい。