[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$。