自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:48:48，当前版本为作者最后更新于2023-11-13 11:28:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

吐槽：原来的题解证的都什么玩意，全撤了。

考虑最暴力的做法，设 $f_{n,j}$ 表示有 $n$ 个物品，还有 $j$ 轮才可以不取时的 SG 函数。但是由于只有一堆，因此我们不注意具体的 SG 函数值，只需要知道其值是否为 $0$ 就可以了。简单来说，$f_{n,j}=1$ 表示先手必胜，$f_{n,j}=0$ 表示先手必败。边界条件显然是 $f_{0,j}=0$。

那么根据必胜状态有必败后继状态，必败状态后继状态全部必胜，我们列出转移方程：

$$\begin{cases} f_{n,j}=[0 \in \{f_{n-i,j-1}:i=1,\dots,m\}],&j\ge1,\\ f_{n,0}=[0 \in \{f_{n,k}\}\cup\{f_{n-i,0}:i=1,\dots,m\}], \end{cases}$$

其中逻辑表达式 $A$ 为真时 $[A]=1$，否则 $[A]=0$。

直接朴素转移是 $O(nmk)$ 的，单次复杂度达到了惊人的 $10^{54}$ 量极！

考虑先打个表找规律。我们发现 $f_{n,j}$ 关于 $n$ 以 $c=(m+1)\cdot\left\lfloor\dfrac k2\right\rfloor+1$ 为循环，换句话说 $\forall n,j,f_{n,j}=f_{n+c,j}$。于是为了求解我们可以先取 $n_0=n \bmod c$。再看看 $f_{n_0,0}$ 的值，也就是我们要的答案，发现 $f_{n_0,0}=0$ 当且仅当 $n_0=0$ 或 $n_0>1$ 且 $n_0\bmod(m+1)=1$。

好了现在你已经可以单次询问 $O(1)$ 时间复杂度 AC 此题了。接下来我们考虑证明。

非常自然地对着 $k+1$ 行的大表想到加强结论，方便我们对着方程嗯推。以下结论中 $n$ 均为 $n \bmod c$ 以后的结果。

加强结论如下：$f_{n,j}=0$ 当且仅当以下两种情况之一成立：

1. $(m+1)\mid n$ 且 $\dfrac n{m+1}\le\left\lceil\dfrac j2\right\rceil$；
2. $n \bmod (m+1)=1$ 且 $\dfrac{n-1}{m+1}>\left\lfloor\dfrac j2\right\rfloor$。

只需证明这个 $f$ 满足上面的方程即可。请读者自行打个 $k \ge 4$ 的大表，后面的事情就是直观的了。注意要证明循环处的衔接情况。

注意特判 $op=1$ 与 $k=1$。