E - 転倒数 Editorial by noimi
前から順番に数列を決めていきます。
初めて \(x_i \neq p_i\) となる \(i\) を固定します。 (\(x_1 = p_1, \ldots, x_{i - 1} = p_{i - 1}\))
このとき、\(x_i < p_i\) です。
\(i + 1\) 番目以降はどのような順列でも条件を満たします。このような順列と \(x_i\) の定め方は、まだ使われていない \(p_i\) 未満の数 \(\times (N - i)!\) です。 \(j < k, x_j > x_k\) という \((j, k)\) の組を三種類に分けて考えます。
\(j < i\)
数列の取り方より、\(x_j\) より前の集合と後ろの集合が定まります。
\(i < j\)
各候補位置に対して、それらが転倒している確率は \(1/2\) です。
\(j = i\)
\(x_j\) をまだ使われていない \(p_i\) 未満の数のうち \(s\) 番目のものとしたとき、このような組は \(s - 1\) 組あります。
二種類目と三種類目はそれぞれ \(O\left(1\right)\) で求まるので、\(1\) 種類目の数を更新しながら \(i = 1, \ldots, N\) と求めていけばよいです。
まだ使われていない \(p_i\) 未満の数を求めるところがボトルネックで、 計算量は BIT などを用いることで \(O\left(N log N\right)\) で解くことができます。
posted:
last update: