\(R_{i} + 1 < L_{i + 1}\) が成り立っていると仮定します。(実装上では適当な圧縮をしてください。)

\(dp[i]\) を \(0\) 以上 \(2^{B}\) 未満の整数であって、\(d = 0, 1, \dots ,B - 1\) に対して以下の条件を満たすものとします。

• \(dp[i]\) の \(2^{d}\) の桁が \(1\) であることと、マス \(i - d\) に到達可能であることが同値

\(dp[N]\) の値が求まれば良いです。

まず、悪いマスがないときのことを考えます。

\(dp[i + 1]\) の値は \(dp[i]\) の値のみに依存して求まります。よってダブリングすることで、 \(dp[i]\) の値がわかっているとき、\(dp[i + a]\) の値が時間計算量 \(O(\log(a))\) で求まります。

上記のことを用いると、 \(dp[R_{i} + 1]\) がわかっているとき、 \(dp[L_{i + 1} - 1]\) が高速に求められます。

\(dp[L_{i} - 1]\) がわかっているとき、\(dp[R_{i}]\) はシフトをすることで簡単に求まります。

マス \(R_{i} + 1\) に到達可能であることは、\(2^{A - 1}\leq dp[R_{i}]\) と同値であるため、 \(dp[R_{i} + 1]\) も簡単に求められます。

以上のことを用いると、 \(dp[N]\) が時間計算量 \(O((M + 2^{B})\log(N))\) で求められます。

c++ 実装例 173ms