Nim问题就是把若干堆火柴进行拿取操作，每次至少拿一根或多根，谁拿了最后一根谁就赢。可是此题还加了一个动作，就是你可以选择不取火柴，而是将一堆超过3根的火柴堆分成三个非零堆，这样的问题叫做“分隔-取走”游戏。刚看此题我是一脸懵逼的，毕竟对博弈论一点没接触过。所以我从网上搜了一下关于博弈论的博客，发现大家关于博弈论都是先把取火柴变为有向图，把每个堆看成是通往顶点的一个点，然后会用到sg这样一个函数来求解的。(文章的末尾会贴上几个介绍博弈论经典问题的链接)
sg值：一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。
下面来介绍一下我所理解的sg函数。sg值就是一个用于描述该游戏是否到达必胜或者必败的一个东西，当sg=0时，表示游戏已经结束，你下一步必输；sg ≠ 0时表示游戏还可以继续进行。所以这道题就是用sg来看这个游戏是否结束。
对于sg值的计算方法，有以下几种：1、对于一个数，如果不进行分堆操作，它的sg值等于它本身。2、对于一个堆的sg，比如m,n,q三个堆，他们的sg（m,n,q）=sg（m）^sg(n)^sg（q）3、还有一种算法就是定义。这种情况是它给了你一个数n的各个后继点的sg值，那么这个数n的sg值就是不等于它的后续点的sg值且大于等于0的最小数。比如后继点的sg值分别为0、1、3、4，那么n的sg就是去掉0、1、3、4之后的最大非负数2。
这里还要再介绍一个概念就是后续点。后续点是指按照题目要求的走法可以走一步达到的那个点。
此外还有异或运算符“ ^ ”，也叫xor。它的运算法则是：给两个数m、n，先把两个数化成二进制数，然后位数上相同的话就的0，不同就得1。举个例子： 1和4，1用二进制写是001，4用二进制写诗100，那么001^100，第一位和第三位不同得1，第二位相同得0，所以得到结果101，也就是5。
至于sg值打表，先把vis数组全都初始化为0，然后遍历每个数的sg值vis[sg值出现过的数]都变为1，代表取石子的过程。然后将所有能拆分的都拆分，即用“^”来拆分sg值。然后当出现sg为0的时候，把其所作为sg的值所对应的那个第几个sg记录下来。找到sg值和x之间的关系
下面贴几个觉得比较好的关于博弈论的链接：
5、取走-分隔问题
6、Sg函数介绍
7、Sg函数模板
京公网安备 11010502036488号