题解 P9486 【「LAOI-1」Bash Game-Plus】

· · 题解

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

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

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

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 当且仅当以下两种情况之一成立：

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

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