Nim 博弈
进阶Nim 博弈是博弈论的入门问题，SG 函数的基础。
// 算法讲解
Nim 博弈
演示 Nim 博弈的 SG 函数计算过程。
待机
速度 中
待机 ⌨1bool nimGame(vector<int>& piles) {
2 int xorSum = 0;
3 for (int x : piles) xorSum ^= x;
4 return xorSum != 0;
5}
复杂度分析
时间 O(n)
空间 O(1)
最优 O(1)
最坏 O(n)
算法讲解
有 n 堆石子，两人轮流从任意一堆中取至少一个，取走最后一个石子的人获胜。
先手必胜当且仅当所有堆的异或和不为 0。
先手必败当且仅当所有堆的异或和为 0（Nim-Sum = 0）。
SG 函数是解决更一般博弈问题的工具。