\(A = B\) のとき

明らかに \(1 \equiv N \pmod A\) が必要です。

\(1 \equiv N \pmod A\) のとき、通るマスはマス \(1, A + 1, 2A + 1, \ldots, N - A, N\) となるため、\(1 \equiv x \pmod A\) なる \(x\) であってマス \(x\) が悪いマスであるようなものが存在するか判定すればよいです。これは各 \(i\) について \(L_i \leq j \leq R_i\) かつ \(1 \equiv j \pmod A\) なる \(j\) が存在するか判定すればよく、\(O(M)\) 時間でできます。

\(A < B\) のとき

マスは全部で \(N\) 個あるため、各マスについて辿り着けるか判定することはできません。そこで、一部のマスのみについて辿り着けるか判定することで高速化を行います。

長さ \(M + 1\) の数列 \(S, T\) を以下のように定めます。

• \(S_1 = 1\)
• \(S_i = R_{i - 1} + 1\) \((i > 1)\)
• \(T_i = L_i - 1\) \((i \leq M)\)
• \(T_{M + 1} = N\)

また、数列 \(I_i\) を \((S_i, S_i + 1, \ldots, T_i)\) として定めます。

\(I_i\) の先頭 \(B\) 項を \(X_i\)、末尾 \(B\) 項を \(Y_i\) とします。ただし、\(I_i\) の長さが \(B\) より短いときは \(X_i = Y_i = I_i\) とします。また、単に数列の要素が表すマスのことを数列のマスというように表記します。

\(X_i\) および \(Y_i\) の長さの合計は \(O(MB)\) であり、これらの数列のマスについてのみ辿りつけるか判定を行うことを目指します。

\(X_1, X_2, \ldots, X_i\) および \(Y_1, Y_2, \ldots, Y_i\) のマスに対して辿り着けるか計算できているとき、\(X_{i + 1}\) のマスに辿り着けるか判定することは各マスについて前 \(B\) マスを見ることで \(O(B^2)\) 時間で簡単に行えます。

\(X_1, X_2, \ldots, X_i\) および \(Y_1, Y_2, \ldots, Y_{i - 1}\) のマスに対して辿り着けるか計算できているとき、\(Y_i\) のマスに辿り着けるか判定することを考えます。これは上と同様に前 \(B\) マスに対して判定した上で、\(X_i\) の各マスから複数回の移動により到達できるか判定すればよいです（悪いマスを \(1\) つ以上飛び越えて到達する場合は前者、そうでない場合は後者により判定できています）。

したがって、間に悪いマスがないときに \(w\) マス進めるか？という問題が \(O(1)\) 時間で解ければこの場合も \(O(B^2)\) 時間で計算が行えます。

\(A < B\) より \(B - 1\) マス進むことと \(B\) マス進むことはできるため、\(w \geq B^2-3B + 2\) のときは \(w\) マス進むことはできます。\(w < B^2-3B + 2\) のときは愚直な \(O(B^3)\) 時間の dp により前計算をしておくとよいです。

以上により全体として \(O(MB^2 + B^3)\) 時間で計算が完了します。実際の実装上は、set や map などを用いた \(\Theta(MB^2 + MB \log(MB) + B^3)\) 時間解法を用いることも有力でしょう。\(\Theta(MB^2 \log(MB) + B^3)\) 時間解法も定数倍が重くないものは AC することを確認しています。