Grundy值

Grunndy值可以将很多博弈游戏转化成NIM博弈的的形式，同样使用异或进行计算。

当前状态的Grundy值是除了任意一步当前状态可以转移到的状态的Grundy值以外的最小非负整数

NIM中具有\(x\)颗石子的石子堆，可以转移到任意小于\(x\)的石子堆\((0,1,\cdots,x-1)\)，也就是可以将任意堆石子变成小于本身数量的形式
Grundy中数值为\(x\)的状态可以转移到任意数值小于\(x\)的状态\((0,1,\cdots,x-1)\)，也就是可以将数值变成任意小于本身数值的形式

NIM中\(x_1\ XOR\ x_2\ XOR\cdots XOR\ x_n\)为零时必败，不为零时必胜
Grundy中同样有\(x_1\ XOR\ x_2\ XOR\cdots XOR\ x_n\)为零时必败，不为零时必胜

通常使用动态规划或者记忆化搜索求解，设状态数为\(x\)，转移方法数为\(k\)，则时间复杂度\(O(x*k)\)

Grundy值

原文：https://www.cnblogs.com/fxq1304/p/13404972.html