AC代碼

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

題意：

山姆一直在教喬恩玩石頭游戲，這個游戲的規(guī)則很簡單：

1. 游戲以n堆標(biāo)記從1到n的石頭開始。第i堆包含si塊石頭。

2. 玩家交替移動。移動被認(rèn)為是從一堆石頭中移除一些石頭。移除0塊石頭不算移動。

3. 不能移動的玩家會輸。

現(xiàn)在喬恩相信他已經(jīng)做好了戰(zhàn)斗的準(zhǔn)備，但山姆并不這么認(rèn)為。

為了證明他的論點(diǎn)，山姆建議他們玩一個修改版的游戲。

在這個修改后的版本中，在一堆上不能進(jìn)行多次相同數(shù)量的移動。

例如，如果從一堆中移除了4塊石頭，則不能再次從該堆中移除4塊石頭。

?

題解：

對于一堆不加限制的X個石頭，SG(X) = X, 但是加了限制后我們需要重新推算SG(X)，首先明確SG(0) = 0;

SG(1) = MEX{SG(0)} = 1 // 唯一的轉(zhuǎn)移方式

SG(2) = MEX{SG(0)} = 1 //是X=2可以轉(zhuǎn)移的唯一方式，因?yàn)槿绻仁秩?，兩次都移動1個不符合要求，故后手仍然輸。

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

// 注意此時SG(3')由于4->3用了1，則SG(3')只能由SG(0)構(gòu)成，則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?

所以我們發(fā)現(xiàn)此時SG(X)和X的整數(shù)劃分有關(guān)，并且劃分出的數(shù)不能一個出現(xiàn)大于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函數(shù)等價于這堆石頭最多可以被取的方法數(shù)。

?