問題そのものの解説ではなく、答えの上界が \(O(N f(K))\) で抑えられる証明を解説します。

明らかに \(M \neq 1\) としてよいです。 一度もスタートに戻らずにゴール出来る確率の下界を \(p\) とすると、答えの上界が \(\frac{N}{p}\) で抑えられます。よってこの \(p\) に注目すればよく。スタートに戻るマス → 止まったらゲームが終わるマス として考えることができます。

「\(p_i =\) マス \(i\) を(死なずに)踏む確率」として、これを配るDPで計算することを考えます。すると次の問題へ言い換えられます。

長さ \(M\) の配列 \([a_1, a_2, \cdots, a_M] = [1, 0, 0, \cdots, 0]\) が与えられる。 次の操作のうちどちらかを行うことを \(N\) 回繰り返す。

• (操作1) 配列の末尾に \(0\) を追加する。配列の先頭の要素を \(\frac{1}{M}\) ずつ先頭以外の要素に足し込む。配列の先頭の要素を削除する。
• (操作2) 配列の末尾に \(0\) を追加する。配列の先頭の要素を削除する。この操作は \(N\) 回のうち \(K\) 回までしか行うことが出来ない。

最終的な配列の要素の総和として考えられ、更に \(0\) ではないもののうち、最小の値はいくつか？(この最小値が \(p\) となる)

この問題を考察すると、まず以下のことがわかります。

• 配列の初期値を \(\left[ \frac{1}{M}, \frac{1}{M}, \cdots, \frac{1}{M} \right]\) としても問題ない。
• 配列は常に広義単調減少である。

そして、次の命題が成立するのが本質です。

• 直前 \(M - 1\) 回の操作のうち操作2を行った回数を \(x\) とする。このとき、\(x \neq M - 1\) ならば、\(a_1 \leq \left(1 + \frac{M}{(M-1)-x} \right) a_2\) が成立する。

証明は次の通りです。

• 操作回数が \(M\) 回未満、あるいは \(M\) 回前の操作が操作2の場合は \(a_1 = a_2\) となり明らかに成立する。
• それ以外の場合も、\(M\) 回前の操作を行う時点での配列を \([1, 0, 0, \cdots, 0]\) としても一般性を失わない。この場合に限定すると、式をいじることで示せる。

この命題により、操作2で配列の総和は高々 \(\frac{M - 1 - x}{3M - 2 - 2x}\) にしかならないことがわかります。あとはこの値を適当に抑えれば良いです、具体的には \(\max \left( \frac{1}{M+2}, \frac{1}{x+4} \right) \geq \max \left( \frac{1}{M+2}, \frac{1}{K+3} \right)\) などで抑えることができます。