Bash

一堆数量为N的石子。 两个玩家轮流进行操作，每次可以从堆中取走不超过 M （M≤N）个石子（必须至少取走一个）。不能进行操作的玩家判负。

1. 核心公式：判断 \(N \bmod (M+1)\) 的结果
   • 若结果为 0 → 先手必败
   • 若结果不为 0 → 先手必胜
2. 必胜策略：
   当 \(N \bmod (M+1) = r \ (r>0)\) 时，先手第一次直接取走 \(r\) 个石子，剩余石子数为 \(k \times (M+1)\)（\(k\) 为正整数）。
   此后无论后手取走 \(x\) 个（\(1 \le x \le M\)），先手都取走 \((M+1)-x\) 个，每一轮都会让石子数减少 \(M+1\) 个，最终先手能取走最后一批石子。

以“输入N和M，输出先手是否必胜”为例：

import java.util.Scanner;

public class BashGame {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 石子总数
        int M = sc.nextInt(); // 每次最多取的数量
        sc.close();
        
        if (N % (M + 1) == 0) {
            System.out.println("先手必败");
        } else {
            System.out.println("先手必胜");
            // 额外输出第一步取的石子数
            System.out.println("第一步取：" + (N % (M + 1)) + " 个");
        }
    }
}

NIM

• 初始状态：三列铜板（或石子），数量分别为 3、4、5，共 12 枚。
• 两人轮流操作，每次只能从某一列中取走至少 1 枚，不能跨列取。
• 拿光最后一枚铜板的人获胜
  后来，大家发现，先取的人只要在3那列里取走2枚，变成了1、4、5（此时1⊕4⊕5=0为必败态），就能稳操胜券了，游戏也就变得无趣了。

NIM 博弈先手必胜，当且仅当 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n \neq 0 \)。注：\( A_i \) 每堆石子的数量

证明： 所有物品都被取光是一个必败局面（对手取走最后一件物品，已经获得胜利），此时显然有 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0 \)。注：\( A_i \) 当前态每堆石子的数量，\( A_i \)=0

对于任意一个局面，如 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = x \neq 0 \)，设 \( x \) 的二进制表示下最高位的 1 在第 \( k \) 位，那么至少存在一堆石子 \( A_i \)，它的第 \( k \) 位是 1。显然 \( A_i \text{ xor } x < A_i \)，我们就从 \( A_i \) 堆中取走若干石子，使其变为 \( A_i \text{ xor } x \)，就得到了一个各堆石子数异或起来等于 0 的局面。

对于任意一个局面，如果 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0 \)，那么无论如何取石子，得到的局面下各堆石子异或起来都不等于 0。可用反证法证明，假设 \( A_i \) 被取成了 \( A_i' \)，并且 \( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_i' \text{ xor } \dots \text{ xor } A_n = 0 \)。由异或运算的消去律得 \( A_i' = A_i \)，与“不能不取石子”的规则矛盾。

综上所述，再由数学归纳法可知，\( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0 \) 为必败局面，一定存在一种行动让对方面临“各堆石子异或起来等于 0”。\( A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n \neq 0 \) 为必胜局面，无论如何行动，都会让对方面临一个“各堆石子异或起来不等于 0”的必胜局面。

证毕。

公平组合游戏 ICG

若一个游戏满足：

1. 由两名玩家交替行动。
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
3. 不能行动的玩家判负。
   则称该游戏为一个公平组合游戏。

NIM 博弈属于公平组合游戏，但常见的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 2 和条件 3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设 \( S \) 表示一个非负整数集合。定义 \( \text{mex}(S) \) 为求出不属于集合 \( S \) 的最小非负整数的运算，即： \[ \text{mex}(S) = \min_{x \in \mathbb{N}, x \notin S} \{x\} \]

mex 函数（最小排斥值）定义与核心规则

\(mex(\{x_1,x_2,\dots,x_n\})\) 指非负整数集合中未出现的最小自然数，自然数的取值范围为 \(0,1,2,3,\dots\)。

核心判断逻辑

从自然数 \(0\) 开始，按从小到大的顺序逐一校验，第一个不在集合中的数即为 mex 函数的结果。

典型示例与规律总结

\(\{0,1,2,3\}\)\(4\) 集合包含 \(0 \sim k\) 连续自然数，\(mex=k+1\)\(\{2,3,6\}\)\(0\) 集合不含 \(0\)，直接返回 \(0\)\(\{0,1,4,5\}\)\(2\) 集合含 \(0,1\) 但缺 \(2\)，忽略后续大数 \(\{0,7,8\}\)\(1\) 集合含 \(0\) 但缺 \(1\)，直接返回 \(1\)

集合元素	mex 计算结果	对应规律

SG函数

在有向图游戏中，对于每个节点 \( x \)，设从 \( x \) 出发共有 \( k \) 条有向边，分别到达节点 \( y_1, y_2, \dots, y_k \)，定义 \( \text{SG}(x) \) 为 \( x \) 的后继节点 \( y_1, y_2, \dots, y_k \) 的 SG 函数值构成的集合再执行 mex 运算的结果，即： \[ \text{SG}(x) = \text{mex}(\{\text{SG}(y_1), \text{SG}(y_2), \dots, \text{SG}(y_k)\}) \]

特别地，整个有向图游戏 \( G \) 的 SG 函数值被定义为有向图游戏起点 \( s \) 的 SG 函数值，即： \( \text{SG}(G) = \text{SG}(s) \)。

有向图游戏的和

设 \( G_1, G_2, \dots, G_m \) 是 \( m \) 个有向图游戏。定义有向图游戏 \( G \)，它的行动规则是任选某个有向图游戏 \( G_i \)，并在 \( G_i \) 上行动一步。\( G \) 被称为有向图游戏 \( G_1, G_2, \dots, G_m \) 的和。

有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和，即： \[ \text{SG}(G) = \text{SG}(G_1) \oplus \text{SG}(G_2) \oplus \dots \oplus \text{SG}(G_m) \]

定理

有向图游戏的某个局面必胜，当且仅当该局面对应节点的 SG 函数值大于 0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的 SG 函数值等于 0。

我们不再详细证明该定理。我们可以这样理解：

• 在一个没有出边的节点上，棋子不能移动，它的 SG 值为 0，对应必败局面。
• 若一个节点的某个后继节点 SG 值为 0，在 mex 运算后，该节点的 SG 值大于 0。这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。
• 若一个节点的后继节点 SG 值均不为 0，在 mex 运算后，该节点的 SG 值为 0。这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。

什么是异或（XOR）？

异或是一种二进制位运算，记作 ⊕，规则如下：

0 0 0 0 1 1 1 0 1 1 1 0

a	b	a ⊕ b

👉 核心性质：

• 相同为 0，不同为 1
• 它是可交换、可结合的：a ⊕ b = b ⊕ a ， (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
  其中：(a ⊕ b) ⊕ c = a ⊕ (b + c) 不成立
• 任何数异或自己等于 0：a⊕a=0
• 任何数异或 0 等于它自己：a⊕0=a

一、取石子

https://ac.nowcoder.com/acm/problem/15972

二、题目描述

现有两堆石子，两人轮流从石子堆中取石子，每次只能取1个、3个或9个石子。游戏规则为：取到最后一个石子的人获胜。
假设先手和后手都会采用最优策略进行操作，请判断在给定两堆石子数量的情况下，先手最终会赢还是输。

三、输入输出描述

（一）输入描述

• 多组输入数据，每组输入占一行。
• 每行包含两个正整数 n1 和 n2（1 ≤ n1 ≤ 100，1 ≤ n2 ≤ 100），分别代表两堆石子的数量。

（二）输出描述

• 对于每组输入，若先手能获胜，则输出“win”；若先手会失败，则输出“lose”。

四、示例

（一）输入

1 1 
1 2

（二）输出

lose
win

使用sg函数解答

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	private static final int[] TAKES = {1, 3, 9};
	private static int[] dp;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextInt()) {
			int xorSum = 0;
			dp = new int[1001];
			Arrays.fill(dp, -1);
			int n1 = scanner.nextInt();
			int n2 = scanner.nextInt();

			xorSum = sg(n1) ^ sg(n2);
			System.out.println(xorSum != 0 ? "win" : "lose");
		}
		scanner.close();
	}

	private static int sg(int x) {
		// 终止状态：x=0，SG值为0
		if (x == 0) {
			return 0;
		}
		if (dp[x] != -1) {
			return dp[x];
		}
		Set<Integer> nextSgSet = new HashSet<>();
		for (int p : TAKES) {
			if (p <= x) {
				nextSgSet.add(sg(x - p));
			}
		}
		// 计算mex值
		int mex = 0;
		while (nextSgSet.contains(mex)) {
			mex++;
		}
		dp[x] = mex;
		return mex;
	}
}