[ABC297G] Constrained Nim 2
SG函数是本篇文章的先决条件。如果您不了解它，请参阅以往的ABC问题的解析文章。（类似问题：ABC255-G）
在一个游戏问题中，尝试实验总是一个好主意。
在这个问题中，我们可以预期\(x\)的 SG \(f(x)\)满足以下公式：
\( \lfloor \frac{x\bmod {(L+R)}}{L}\big\rfloor. \)
如果这个猜想成立，那么这个问题可以在 \(\mathrm{O}(N)\) 的时间内解决。
现在我们来证明这个猜想是正确的。
（1）如果 \(x < L+R\)
-
如果 \(0\leq x <L\)，无法进行移动，所以 \(f(x)=0\)。
-
如果 \(L\leq x <2L\)，则由于 \(x < L+R\)，所以 \(x-R < L\)，可以转移到格兰迪数为 \(0\) 的状态。此外，$ x - L < L$，所以无法转移到格兰迪数为 \(1\) 的状态。因此，\(f(x)=1\)。
-
如果 \(2L\leq x <3L\)，则由于 \(x < L+R\)，所以 \(x-R < L\)，可以转移到格兰迪数为 \(0\) 的状态。此外，左端点 \(L\le x-L\le 2L\)，可以转移到 \(1\)，则 \(0\sim 1\) 都有了，\(f(x)=2\)。
-
如果 \(3L\leq x <4L\)，则由于 \(x < L+R\)，所以 \(x-R < L\)，可以转移到格兰迪数为 \(0\) 的状态。此外，左端点 \(2L\le x-L\le 3L\)，可以转移到 \(2\)，则 \(0\sim 2\) 都有了，\(f(x)=3\)。
通过重复上述讨论，我们可以证明对于 \(x<L+R\)，有 \(f(x)=\lfloor \frac{x}{L}\big\rfloor\)。
（2）如果 $ L+R\leq x < 2(L+R)$
-
如果 \(L+R\leq x < L+R+L\)，则由于 \(L\leq x-R<2L\)，因此 \(R\leq x-L<L+R\)，无法转移到格兰迪数为 \(0\) 的状态。因此，\(f(x)=0\)。
-
如果 \(L+R+L\leq x < L+R+2L\)，根据相同的讨论，可以转移到格兰迪数为 \(0\) 的状态（\(L+R\leq x-L < 2L+R\)），但是 \(L+R+L\le x\rightarrow X-R\ge 2L\)，所以无法到 \(1\)，\(f(x)=1\)。
对于所有满足 $ L+R\leq x < 2(L+R)$ 的 \(x\)，相同的讨论成立。因此，对于 $ L+R\leq x < 2(L+R)$，有 \(f(x)=\lfloor \frac{x\bmod {(L+R)}}{L}\big\rfloor\)。
（3）一般情况
如果 \(2(L+R)\leq x\)，那么在我们的情况下，格兰迪数 \(f(x)\) 只取决于 \(f(x-R),f(x-R+1),\ldots,f(x-L)\)。根据（2）（可以直接将（2）中的当作（1），相当于全部往前移动 \(L+R\)，等价），一般情况下有 \(f(x)=\lfloor \frac{x\bmod {(L+R)}}{L}\big\rfloor\)。