核心逻辑与数学原理
博弈论（Game Theory）是离散数学中研究具有对抗性质决策交互的理论。在 NOIP 竞赛中，考察的边界高度集中于公平组合游戏（Impartial Combinatorial Games, ICG）。
1. 公平组合游戏（ICG）的特征
一个游戏被称为公平组合游戏，必须满足以下硬性约束：
- 游戏有两名玩家，双方轮流进行决策。
- 在任意一个确定的游戏状态（State）下，当前合法移动集合（Legal Moves）仅取决于状态本身，与当前处于哪一个玩家的轮次无关（象棋不属于 ICG，因为黑方只能走黑子，红方只能走红子）。
- 游戏在有限步内必然结束，且不允许出现无意义的循环。
- 通常采用正常分配规则（Normal Play Convention）：最后一个做出合法移动的玩家获胜（即无法移动者判定为输）。
2. 状态空间划分：P-position 与 N-position
在 ICG 的状态空间拓扑图中，所有的游戏状态可以被严格且唯一地划分为两类：
- P-position（Previous-position）：必败状态。意味着刚走完最后一步的玩家（即前一个玩家）处于必胜局势，当前轮到的玩家面对此状态必败（若双方均采取完美策略）。
- N-position（Next-position）：必胜状态。意味着当前即将做出移动的玩家（下一个玩家）存在某种策略使其必胜。
状态判定的三大公理
根据倒推归纳法（Backward Induction），状态的本质由以下三条底层逻辑锁定：
- 终结状态必为 P 状态：所有无法做出任何合法移动的终止状态，均为 P-position（根据无法移动者输的规则）。
- 可达 P 必为 N：如果从当前状态出发，存在至少一种合法的移动能转移到某个 P-position，则当前状态为 N-position（当前玩家只需果断将这个必败态抛给对手，自己即可获胜）。
- 后继皆 N 必为 P：如果从当前状态出发，无论做出何种合法移动，得到的后继状态全部都是 N-position，则当前状态为 P-position（当前玩家无论怎么挣扎，对手面对的都是必胜态）。
算法推导与状态设计
状态图的拓扑记忆化搜索
对于局势相对简单、状态可以被数值量化的博弈游戏，我们可以将游戏的所有可能状态抽象为有向无环图（DAG）上的节点，合法移动抽象为有向边。
-
状态设计：定义一维或多维状态数组
f[state]，其取值定义为： -
0：表示该状态为 P-position（必败态）。 -
1：表示该状态为 N-position（必胜态）。 -
状态转移方程：
$$f[u] = \bigvee_{(u, v) \in E} \big( f[v] == 0 \big)$$
代数含义：对节点 $u$ 的所有后继节点 $v$ 进行逻辑或（OR）运算。只要后继中有一个是必败态（$f[v]==0$），当前就是必胜态（$f[u]=1$）；如果所有后继均为必胜态，则当前为必败态。
- 计算序：使用记忆化搜索（Memoization）。由于游戏必然在有限步内终结，该 DAG 天然自带无环特征。从初始局势出发向下搜索，遇到出度为 $0$ 的终止态直接返回
0，层层回溯即可。
C++ 标准源码
以下源码展示了如何通过记忆化搜索，对一个典型的博弈状态图进行 P/N 状态判定。
#include <iostream>
#include <vector>
#include <cstring>
const int MAXS = 10000;
int f[MAXS + 5]; // 状态记忆化数组：-1 表示未计算，0 表示 P-position，1 表示 N-position
// 获取当前状态的所有合法后继状态（示例：每次可以减去 1, 3, 或 4）
std::vector<int> get_next_states(int state) {
std::vector<int> next_states;
if (state >= 1) next_states.push_back(state - 1);
if (state >= 3) next_states.push_back(state - 3);
if (state >= 4) next_states.push_back(state - 4);
return next_states;
}
// 记忆化搜索判定 P/N 状态
int judge_position(int state) {
if (f[state] != -1) return f[state]; // 拦截已计算状态
std::vector<int> next_moves = get_next_states(state);
// 边界公理 1：无法移动的终止状态必为 P-position
if (next_moves.empty()) {
f[state] = 0;
return 0;
}
// 遍历所有可能的后继移动
for (int next_state : next_moves) {
// 公理 2：只要后继状态中存在一个必败态(P)，当前状态就转化为必胜态(N)
if (judge_position(next_state) == 0) {
f[state] = 1;
return 1;
}
}
// 公理 3：所有后继移动全部走向必胜态，当前玩家无路可逃，当前状态为必败态(P)
f[state] = 0;
return 0;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::memset(f, -1, sizeof(f)); // 初始化状态表为 -1
int t;
if (std::cin >> t) {
while (t--) {
int initial_state;
std::cin >> initial_state;
if (judge_position(initial_state) == 1) {
std::cout << "First player wins (N-position)\n";
} else {
std::cout << "Second player wins (P-position)\n";
}
}
}
return 0;
}NOIP 实战避坑指南
- 混淆 P 状态（必败）与 N 状态（必胜）的代数归宿 在编写博弈论搜索时，经常有选手在判断条件上写反。务必死记：当前是 N，当且仅当后继有 P。很多选手误写成“后继全为 P 才是 N”，直接导致整个博弈树的胜负逻辑发生完全对调。
- 多组询问下忘记重置或错误重置记忆化数组
如果博弈游戏的规则（如每次允许取走的石子集合）在不同的输入数据中是会发生改变的，那么上一次询问得到的
f数组局势绝对不能沿用到下一次询问中。必须在每组测试数据输入时使用std::memset(f, -1, sizeof(f))进行彻底洗牌，否则会引发严重的跨数据状态污染。
经典 NOIP/洛谷 真题
1. 洛谷 P1290 黄金分割数游戏
- 题意描述：有两个正整数 $(a, b)$，且 $a \ge b$。两个玩家轮流进行操作，每次操作可以用大数减去小数的任意正整数倍，且减完后的结果不能为负数。先将其中一个数变为 $0$ 的玩家获胜。求先手是否必胜。
- 问题本质：带决策分支控制的欧几里得博弈模型。
- 核心解题思路：这道题的形式极其类似于辗转相除法。设当前状态为 $(a, b)$。
- 若 $a < 2b$，当前玩家只有一种唯一的合法移动，即只能变成 $(b, a - b)$，直接递归向下判定。
- 若 $a \ge 2b$，当前玩家面对着巨大的决策权。他可以选择将局势转换为 $(b, a \bmod b)$ 或者 $(b, a \bmod b + b)$。在这两个连续的后继状态中，必然存在一个 P 状态和一个 N 状态。拥有选择权的先手只需要果断把那个 P 状态抛给对手，自己就立于不败之地。因此，只要谁先遇到了 $a \ge 2b$ 的局势，谁就锁定了胜局。
2. 洛谷 P2148 [SDOI2009] E&D
- 题意描述：游戏中有好几堆石子，每堆石子由两个正整数 $(x, y)$ 组成。每次操作可以选择一堆石子 $(x, y)$，将其消灭，然后把剩下的石子分成两堆全新的石子 $(x_1, y_1)$ 和 $(x_2, y_2)$，满足 $x_1+x_2=x$ 且 $y_1+y_2=y$。无法操作者输。
- 问题本质：状态拆解下的博弈分析（后续会引入 SG 函数，但其根基依旧是 P/N 判定）。
- 核心解题思路：可以通过小范围的数据跑一遍上文给出的记忆化搜索源码，打印出 $(x,y)$ 较小时的 P/N 状态表。通过观察打表出来的矩阵形态，可以清晰地捕获到规律：状态的胜负规律与 $(x-1) \mid (y-1)$ 的二进制最低位（
lowbit）具有极强的代数映射。在赛时，利用 P/N 判定源码进行小规模打表找规律，是解决复杂博弈论题目最高效的得分手段。