本質的には公式解説と同様だと思います．

\(S\) に対応するヤング図形を考えましょう．（公式解説の図も参考にしてください．）このとき，ヤング図形のマスの個数と転倒ペアの個数が一致していることがわかります．

では，転倒ペアを一つ選び入れ替える操作はヤング図形上ではどのような操作に対応しているでしょうか．これは，選んだ転倒ペアに対応したマスのフックを削除する操作と対応していることがわかります.

ここでマス \((a,b)\) のフックとは，\(i \geq a\) かつ \(j =b\) または \(i=a \) かつ \(j\geq b\) を満たすようなマス \((i,j)\) の集合です.

ここまでの考察を元に期待値を求めましょう．初期状態のヤング図形を考え，各マスについてそのマスが操作で選ばれる確率を求めます．

ここで，あるマスが選ばれる確率はそのマスの左上にあるマスにしか依存しません． \(h\times w\) の長方形について右下のマスが選ばれる確率を \(f(h,w)\) としましょう．このとき \(f\) について以下の関係式が成り立ちます．

\[f(h,w) = \frac{1}{hw} + \frac{(h-1)(w-1)}{hw}f(h-1,w-1)\]

これで \(\mathrm{O}(N^2)\) 時間の解法が得られました．ここで \(f\) の値を観察すると \(f(h,w) = \frac{1}{\max(h,w)}\) であると予想できます．そしてこの予想は帰納法により証明できます．

ここまでくれば， \(\frac{1}{i}\) の累積和を前計算し， \(f\) をまとめて計算することで \(\mathrm{O}(N)\) 時間の解法が得られます．