前から順番に数列を決めていきます。

初めて \(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)\) で解くことができます。