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] 黑白棋 题解 。