操作の対称性を考えると、ある時点で黒いボールが最も左にある確率を \(p\) としたとき、左から \(2, 3, \dots ,N\) 番目にある確率はどれも \(\displaystyle \frac{1 - p}{N - 1}\) です。そのため、 \(K\) 回操作をした後に黒いボールが最も左にある確率が求まれば、この問題を解けます。これは動的計画法で求められます。

• \(\mathrm{dp}[i] := i\) 回操作をしたとき黒いボールが最も左にある確率

と定義します。求めたいものは \(\mathrm{dp}[K]\) です。遷移には、以下の \(2\) つの確率が必要です。

• 黒いボールが最も左にある状態から \(1\) 回操作して、黒いボールが最も左以外のどこかに移動する確率
• 黒いボールが最も左以外のどこかにある状態から \(1\) 回操作して、黒いボールが最も左に移動する確率

それぞれ \(p, q\) とします。DP の遷移は以下の通りです。

• \(\mathrm{dp}[0] = 1\)
• \( \mathrm{dp}[i+1] = (1 - p) \mathrm{dp}[i] + q(1 - \mathrm{dp}[i])\)

\(p, q\) は単純な場合の数の計算で

• \(\displaystyle p = \frac{2(n - 1)}{n^2}\)
• \(\displaystyle q = \frac{2}{n^2}\)

とわかります。これを素直に実装すると計算量 \(\mathcal{O}(K)\) の解法が得られます。整理すると \(2\) 項間線形漸化式の形になり、一般項を簡単な形で表現できます (高校数学の典型的な問題です) 。累乗の計算がボトルネックとなり、 \(\mathrm{dp}[K]\) は計算量 \(\mathcal{O}(\log K)\) で求まります。

実装例 (C++)

より一般に、線形漸化式の第 \(N\) 項を求める高速な方法として、行列累乗や Fiduccia のアルゴリズムがあります。