Nim 游戏
\(n=2\) 的时候可以用一个巧妙的方法证明：如果两堆石子一样多，则后手可以通过在另一堆上一直模仿先手的行为获胜；如果两堆石子不一样多，则先手可以在第一次取时把两堆变成一样多。
结论中出现异或的原因（异或的定义为）：
\[a \oplus 0 = a \]\[a \oplus a = 0 \]\[a \oplus b = b \oplus a \]\[a \oplus b \oplus c = a \oplus (b \oplus c) \]关键：必胜态可以到达必败态；必败态只能到达必胜态。
从小情况出发思考，如 \(n = 2, a_i = 2\)；
还可以打表。
- 例一：
\(n=2\) 的时候依旧可以下模仿棋，只是在最后一步取 \(0\) 即可。
-
公平组合游戏：
SG 函数
局面的合并：面前有两盘棋，任选一盘下一步。（Nim 中的不同堆）
定义 SG 函数。
\(\text{mex}\) 函数：返回当前局面不能转移到的 SG 的最小非负整数。
Nim 可以增大。
- 例一：
-
分裂游戏：瓶子不好转移。以“豆”为局面，相当巧妙。（其实还有点不理解。。。局面之间相互难道不应该独立么？）
-
例三：
结束条件不满足公平组合游戏。通过修改结束条件为“剪出 \(1 \times k\) 的长方形的失败”使其与失败相关，转化为公平组合游戏。
平局
此时，状态的转移不再是一个 DAG，而可能出现环。
我们从终止状态出发，倒推出每个状态的胜负情况。对于一个必败态，所有能到达它的点都是必胜态。如果一个点的能到的所有点都是必胜态，则它为必败态。该过程结束后，所有还未确定状态的点即为平局。
阶梯 Nim
P3480 [POI2009] KAM-Pebbles
“差分”
k-Nim
P2490 [SDOI2011] 黑白棋
杂题
- ABC278G Generalized Subtraction Gam
-
如果 \(k, n\) 奇偶性相同，划掉对称部分做模仿棋，先手必胜
-
否则 \(l=r\) 且 \(l, n\) 奇偶性不同，\(O(n^2)\) 暴力。
- AGC017D Game on Tree
比较简单的树型博弈论 dp。
- CF1704F Colouring Game
总之先需要想出一个贪心。但是后面没太听懂。。。
- P3179 [HAOI2015] 数组游戏
前面还是没懂。我应该是搞不清楚局面的真实含义。（不同的“局面”间是否一定要独立？）
二次数论分块很妙。
- P8347 「Wdoi-6」另一侧的月
找规律题。
标签：游戏,Nim,必败,博弈论,笔记,网课,必胜,oplus,SG From： https://www.cnblogs.com/David-Mercury/p/18173534