「振り出しに戻る」のマスが \(M\) マス以上連続している部分が存在することと、マス \(N\) に到達不可能であることは同値です。そのような判定は容易なので、以下ではマス \(N\) に到達可能な場合を考えます。

\(f(i)\) を、マス \(i\) にいるときマス \(N\) に到達するまでの手数の期待値とします。

まずは「振り出しに戻る」のマスがない場合を考えてみましょう。 この場合、\(f(i)=\dfrac{1}{M}(f(i+1)+\ldots+f(i+M))+1\) という等式がなりたちます。よって、累積和を計算しながら \(i\) の大きい順に \(f(i)\) を求めることで \(O(N)\) で\(f(0)\) を求めることができます。

「振り出しに戻る」のマスがある場合を考えてみましょう。 この場合、

\(f(i)= \begin{cases} f(0) & \text{マス i が 「振り出しに戻る」のとき} \\ \dfrac{1}{M}(f(i+1)+\ldots+f(i+M))+1 & \text{そうでないとき} \end{cases} \)

となります。先程とは異なり、\(f(i)\) の関係式が循環しているため、うまく求めることはできないように見えます。

解法1　1次式を持つDP

変数 \(X\) を用いて、\(1\) 次式を値にもつ関数 \(g\) を次のように定めます。

\(g(i)= \begin{cases} X & \text{マス i が 「振り出しに戻る」のとき} \\ \dfrac{1}{M}(g(i+1)+\ldots+g(i+M))+1 & \text{そうでないとき} \end{cases} \)

このようにすると関係式の循環は解消され、「振り出しに戻る」がないときと同様に \(g(i)\) を求めることができます。

\(g(0)=A*X+B\) と表されますが、\(X\) に \(f(0)\) を代入すると \(g\) の定義から \(g\) は \(f\) と等しくなるので、\(f(0)=g(0)=A*f(0)+B\) となります。この1次方程式を解くことで \(f(0)\) を求めることができました。

計算量は \(O(N)\) です。

解法2　二分探索

定数 \(P\) を用いて、関数 \(h\) を次のように定めます。

\(h(i)= \begin{cases} P & \text{マス i が 「振り出しに戻る」のとき} \\ \dfrac{1}{M}(h(i+1)+\ldots+h(i+M))+1 & \text{そうでないとき} \end{cases} \)

このようにすると関係式の循環は解消され、「振り出しに戻る」がないときと同様に \(h(i)\) を求めることができます。

このとき、次が成り立ちます。

• \(P\geq f(0)\) ならば \(h(0)\leq P\)
• \(P\leq f(0)\) ならば \(h(0)\geq P\)

(解法1の \(g\) において\(A\leq 1\) であることに留意して、\(X\) に \(P\) を代入することで示せます)

このことから、二分探索により \(f(0)\) を求めることができます。今回の制約の下では \(f(0)\) は最大で \(N4^K/2≒5\times 10^{10}\) 程度になるので、探索範囲の上限の設定には注意してください。

二分探索の内部で \(O(N)\) のDPを行うので、イテレーション数を \(T\) として計算量は \(O(NT)\) です。

この問題では、相対誤差の方が絶対誤差より小さいので、相対誤差が小さくなるように中央を \((low + high)/2\) ではなく \(\sqrt{low \times high}\) に設定すると、イテレーション数を削減することができます。

なお一般に、二分探索において上限が不明な場合は、上限として適切な値かどうかを \(1\to 2 \to 4\to 8\to\ldots\) のように指数的に調べていくとよいです。