問題を言い換えます。最終的な数列は以下のような手続きにより生成された数列 \(B\) であると考えることが出来ます。

• \(K\) 要素の(多重)集合 \([a_1, a_2, \dots, a_K]\) 、空の配列 \(B\) を考える。以下の操作を \(i = 1, 2, \dots, N - K\) について行う

  • 集合からランダムに要素を一つ取り出し、\(B\) の末尾に追加する。
  • 集合に \(a_{i + K}\) を追加する。

• そして最後に、集合に残った \(K\) 要素をランダムに並び替え、\(B\)の末尾に追加する。

ここで、\(f(i) = \max(i - K, 0)\) と置きます。 これは、\(a_i\) は \(f(i)\) 回目の操作で集合に追加されるという意味です。

あるペア \(i, j(i < j)\) について、最終的な数列で \(a_i, a_j\) が入れ替わっている確率に注目します。

もし \(2\) つの要素が同時に集合に入ったタイミングがあったならば、操作の性質上 \(a_i, a_j\) のどちらが最終的な数列で先になるかは等確率です。 また、同時に集合に入るタイミングの存在する確率は、\(p = (K - 1) / K\) として、\(p^{f(j) - f(i)}\) です。よって、\(a_i, a_j\) が入れ替わる確率は \(\frac{p^{f(j) - f(i)}}{2}\) です。

以上をまとめ、更に式を整理すると、この問題の本質は、

• \(a_i > a_j\) を満たすペア \((i, j)\) についての、\(p^{f(j) - f(i)} = \frac{p^{f(j)}}{p^{f(i)}}\) の総和を求める

ということになります。これは \(j\) を固定すると、\(i < j, a_i > a_j\) を満たす全ての \(i\) について \(\frac{1}{p^{f(i)}}\) の総和を求めよ、となります。よってFenwick Treeにより(転倒数を数えるのと同様のアルゴリズムで)計算可能です。