# 从零开始的博弈论
# 何为博弈论
相关链接：[[异或]]

反 Nim 游戏

对于一个游戏，当一个人无法取时则胜利

结论：

  • 当场面上 $\forall i,a_i=1$ 时，若 $\mid a\mid \mod 2=0$ 时则必胜，否则必败
  • 当场面上存在一个位置使得 $a_i > 1$ 时，若 $\oplus_{i}a_i \not = 0$ 则先手必胜，否则必败
    考虑证明

对于结论一是好证的

对于结论二，则每一步先手都必定能够构造出一种方式使得 $\oplus_{i}a_i=0$ ，而后手则一定不能，由于当前局面并非所有数都为 $1$ ，且会留给后手一个异或和为 $0$ 的状态，故此时后手的局面中必然存在 $\ge 2$ 个非 $1$ 的数，于是最后面一定会留给先手一个有且仅有一个数使得其 $> 1$ 的情况，此时就可以随意控制其到上一个结论了

当遇见与异或相关的 SG 函数时，可以考虑将其往线性基上面去靠 New Nim

博弈论不一定要推奇奇怪怪的式子，也有可能从最朴素的 dp 出发也能达到推出类 SG 函数的状态式，而且就大部分题目而言的话还是 dp 占大头

博弈论问题，可以尝试将元素分组，利用二分图一类的性质，选择一边时就直接选择另一边 偶遇两人选数取min相减，实力强悍强如怪物，拼尽全力也无法战胜