AC代码

https://codeforces.com/contest/768/submission/180701055

题意：

山姆一直在教乔恩玩石头游戏，这个游戏的规则很简单：

1. 游戏以n堆标记从1到n的石头开始。第i堆包含si块石头。

2. 玩家交替移动。移动被认为是从一堆石头中移除一些石头。移除0块石头不算移动。

3. 不能移动的玩家会输。

现在乔恩相信他已经做好了战斗的准备，但山姆并不这么认为。

为了证明他的论点，山姆建议他们玩一个修改版的游戏。

在这个修改后的版本中，在一堆上不能进行多次相同数量的移动。

例如，如果从一堆中移除了4块石头，则不能再次从该堆中移除4块石头。

题解：

对于一堆不加限制的X个石头，SG(X) = X, 但是加了限制后我们需要重新推算SG(X)，首先明确SG(0) = 0;

SG(1) = MEX{SG(0)} = 1 // 唯一的转移方式

SG(2) = MEX{SG(0)} = 1 //是X=2可以转移的唯一方式，因为如果先手取1，两次都移动1个不符合要求，故后手仍然输。

SG(3) = MEX{SG(0),SG(1),SG(2)} = 2

// 注意此时SG(3')由于4->3用了1，则SG(3')只能由SG(0)构成，则SG(3') = 1;

SG(4)  = MEX{SG(0),SG(1), (SG(3') } = MEX{0,1,1} = 2 

SG(5) = MEX{SG(0),SG(1),SG(2),SG(3'),SG(4'))} = MEX{0,1,1,1,1} = 2 

所以我们发现此时SG(X)和X的整数划分有关，并且划分出的数不能一个出现大于1次。

SG(6) = MEX{SG(0),SG(1),SG(2),SG(3'),SG(4)，SG(5')} = MEX{0,1,1,0,2，2} = 3 

即SG(6) = {(0+6), 1+2+3} = 3;

SG(7) = {(0+7),1+2+4} = 3;

即此时SG函数等价于这堆石头最多可以被取的方法数。