期待値を DP のキーに直接設定する方法です．

\(\mathrm{dp}[i] =\)（\(i\) 回操作を行った後の，黒いボールが左から何番目にあるかを表す値の期待値）という DP を行います．このとき，初期値は \(\mathrm{dp}[0] = 1\)，答えは \(\mathrm{dp}[K]\) となります．

遷移の方法を考えましょう．黒いボールが移動しない場合と，移動する場合に分けて考えます．

まず黒いボールが移動しない場合です．この場合は，次に示す \(2\) つの場合があります．

• \(a, b\) が両方とも白いボールのある位置を示した場合．
• \(a, b\) が両方とも黒いボールのある位置を示した場合．

\(a, b\) それぞれについて選ぶ位置を考えることにより，前者の確率は \(\frac{(N-1)^2}{N^2}\)，後者の確率は \(\frac{1}{N^2}\) となることがわかります．よって，確率は合計して \(\frac{N^2 - 2N + 2}{N^2}\) となります．

次に，黒いボールが移動する場合です．この場合は，先ほどと同様に考えることにより，今自分の黒いボールがある位置を \(j\) としたときに，\(i = 1, 2, \dots, j - 1, j +1, \dots, N - 1, N\) のそれぞれに移動する確率が \(\frac{2}{N^2}\) となることがわかります．

よって，DP の遷移は次のように行えることがわかります．

• \(\mathrm{dp}[i + 1] = \mathrm{dp}[i] \times \frac{N^2-2N+2}{N^2} + \sum_{k \neq j} k \times\frac{2}{N^2}\)

しかし，このままでは遷移に \(j\) の情報が必要となってしまうため，遷移を行えません．そこで，この式を次のように変形します．

• \(\mathrm{dp}[i + 1] = \mathrm{dp}[i] \times \frac{N^2-2N+2}{N^2} + \sum_{k} k \times\frac{2}{N^2} - j \times \frac{2}{N^2}\)

ここで，改めて \(j\) の意味を考えてみると，「今黒いボールがある位置」という意味でした．そのため，実はこの値（の期待値）は，既に \(\mathrm{dp}[i]\) に現れています．したがって，この式はさらに次のように変形できます．

• \(\mathrm{dp}[i + 1] = \mathrm{dp}[i] \times \frac{N^2 - 2N + 2}{N^2} + \sum_{k} k \times\frac{2}{N^2} - \mathrm{dp}[i] \times \frac{2}{N^2}\)

結局，DP の遷移を表す式は次のような形で書けることがわかります．

• \(\mathrm{dp}[i + 1] = \mathrm{dp}[i] \times \frac{N-2}{N} + \frac{N + 1}{N}\)

あとは，この式に従って \(\mathrm{dp}[K]\) の値を計算すればよいです．