来源

今天遇到这么个算法题

1	C++编程，取石子游戏.一堆石21个石子.玩家1跟玩家2轮流取1-4的石子.取走最后一个石子的玩家失败.

正确答案:

后手必胜

第一名玩家取了x颗之后，第二名玩家每次取5-x枚石子

这样就能保证先手玩家最后必定只能取1枚石头

记得算法课上老师讲过一些内容，但在考试的时候没有做出来

然后便问了弄ACM的同学，他告诉我这是一道博弈论题

后来又衍生到另外一道类似的题目

问题描述如下

有两个盘子分别放有 5 个和 7 个小球，两个朋友玩游戏：每个人轮流从两个盘子中拿小球，每人每次只能从其中一个盘子中拿，每次可以拿 1 个或者多个（不能一个都不拿），拿到最后一个小球的人算输。问开局先手和后手是否有必胜策略？如果有，请描述必胜策略？

又问了那个同学，其告知是nim游戏的一种，一堆可以用sg函数，多堆可以用异或+SG函数

遂研究之

SG函数

$Nim$游戏的规则:有$n$堆石子，第$i$堆石子有$a_i$个，每次可以从某一堆中取走若干个，先后手轮流取，最后无石子可取的人负

结论：将$n$堆式子的数量异或起来，（即$a_1 \space xor \space a_2 \space xor \space \cdots \space xor \space x_n$）,假如为0，那么先手必败，否则先手必胜