P6639 「JYLOI Round 1」让为哪个？

P6639 「JYLOI Round 1」让 大意 现在有多堆石子，其中第 \(k\) 堆石子有 \(p_k\) 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 \(i\) 为在这次取之前这堆石子的个数，\(j\) 为这次要取的石子数，\(R\) 为给定的常数，则需满足以下条件： \[1 \leq i + j \leq R,i \geq j \geq 1 \] 使对方无法操作者即为胜者。 思路 我们首先考虑这个玩意的 \(SG\) 函数，太坑了，你们可以手动的模一下。 我们来假设 \(R = 5\) 的情况，首先 \(SG(0) = 0\)，\(SG(1) = 1\)，\(SG(2) = 2\)，但是我们发现，当 \(i = 3\) 的时候，能取的只有 \(1, 2\)，取这两坨只会把必胜态留给对面，那这个时候的 \(SG(3) = 0\)，那再看 \(SG(4) = 1\)，然后 \(SG(5) = 0\)，当 \(i \ge R\) 的时候 \(SG(i) = 0\)，这是显然的。 我们对于这个继续看其规律，不难通过注意或者推理得知，当且仅当 \(i \le \lfloor \frac{R}{2} \rfloor\) 的时候，\(SG(i) = i\)，实际上就是简单的 Nim 博弈，但是一旦到达 \(\lfloor \frac{R}{2} \rfloor + 1\)，则 \(SG(\lfloor \frac{R}{2} \rfloor + 1) = 0\)，这是巧合吗？显然不是，但是只有这一个转折点吗？ 我赛时最初的思路是 \(SG(i) = i \pmod {\lfloor \frac{R}{2} \rfloor + 1}\)，可是真的对吗？不难发现当 \(R = 100\) 时，转折点在 \(\lfloor \frac{R}{2} \rfloor + 1 = 51\)，但是当 \(i = 76\) 的时候呢？我们只能取 \(24\)，也就是只能取到 \([52, 75]\) 这个区间，而这个区间的 \(SG\) 是 \({1, 2, 3, \cdots 24}\)，所以 \(SG(76) = 0\)，所以我刚刚的结论是错误的，继续向后模拟，发现在 \(SG(89) = 0\)，不难发现，什么时候等于 \(0\) 呢，我们设 \(pos\) 表示上次的位置，那么有： \[nxt = \lfloor \frac{pos + R}{2} \rfloor + 1 \] 这个说明了，我们的 \(SG\) 是一段一段的，最多有 \(\log\) 段，故我们可以直接向后跳，提前预处理所有段，在查询的时候直接二分所在段，\(\mathcal{O}(1)\) 处理询问即可。