K–Nim 游戏

K–Nim 游戏是 Nim 游戏的推广。

描述

有 \(n\) 堆石子，其中第 \(i\) 堆有 \(a_i\) 个，每次可以从 \(1\) 到 \(k~(k \le n)\) 堆石子中取走任意个石子，不能操作者失败。

结论

记 \(x\) 二进制下的第 \(i\) 位为 \((x)_i\) ，若对于任意 \(s\) 均有 \[ \sum_{i=1}^n\left(a_i\right)_s \equiv 0\pmod{k+1} \] 则先手必败；否则先手必胜。

换言之，只要 \(a_i\) 在二进制下某一位的和模 \(k+1\) 为不为 \(0\) ，先手必胜。

证明 考虑证明上述策略可以将 K–Nim 游戏转化为有向图游戏。

记先手必胜态为 \(\rm N\) ，必败态为 \(\rm P\) 。有向图游戏有如下性质：

1. 终止状态为 \(\rm P\) 。
2. \(\rm P\) 的后继均为 \(\rm N\) 。
3. \(\rm N\) 的后继存在至少一个 \(\rm P\) 。

那么我们只需证明最优策略满足以上性质即可：

1. 所有堆为 \(0\) 是终止状态，显然为 \(\rm P\) 。得证。

2. 一次操作必然会取走一些棋子，但是对于二进制下同一位，至多改变 \(k\) 个位置

   因此 \(\rm P\) 状态不存在一种方案使得 \(\sum_{i=1}^n\left(a_i\right)_s \equiv 0\pmod{k+1}\) 。得证。

3. 同理可知，只要我们取走所有 \(\sum_{i=1}^n\left(a_i\right)_s \not\equiv 0\pmod{k+1}\) 的位置就可以转化为 \(\rm P\)

   记 \(b_s = \sum_{i=1}^n\left(a_i\right)_s\) ，设模 \(k+1\) 不为 \(0\) 的位置分别是 \(s=r_1,r_2\cdots r_m\) ，

   每次我们找到 \(b_{r_i}\) 个石子数不少于 \(2^{r_i}\) 的堆（显然有不少于 \(b_{r_i}\) 个这样的堆），标记要取 \(2^{r_i}\) 即可。\(\square\)

例题

参考 洛谷P2490 [SDOI2011] 黑白棋 题解 。