硬币游戏Ⅲ做题心得

研究了一天终于会写了，故在自己研究并ac后简略提供下解题思路。

官方题解中，"这样我们就转化为k堆独立的硬币问题"是最让我迷惑的地方，这里错了，应改为"转化成n堆独立的硬币问题"。
IOI2009中国集训队论文 有一篇关于SG函数的论文中提出的翻硬币问题就是本题的背景。

翻硬币问题可以转化为若干0加一个1的串的子游戏，而这类题目属于Multi-SG问题，每次翻硬币等价于把一个子游戏又分为更多的子游戏，子游戏的sg函数为所有子子游戏的异或和。

比如样例1001001001，可以转化为四个子问题。
1
0001
0000001
0000000001
所以只需要算出上述四个子问题的SG函数异或和是否为0即可

那么现在只需要研究每个子游戏的SG函数，假设没有k的限制。
SG(0)=0;
SG(1)=mex{SG(0})
SG(01)=mex{SG(0},SG(1})
SG(001)=mex{SG(0},SG(01},SG(01}^SG(1))
SG(0001)=mex{SG(0},SG(001},SG(001}^SG(01),SG(001}^SG(01)^SG(1))
...

这里我们可以打表看看SG函数，发现SG函数如下表

可以发现SG[i]=lowbit(i),再打表看i,SG[i],lowbit(i)三者关系，果真如此。
那么k只是限制了转移的状态，稍微修改下打表程序，用不同的n和k来实践，可以发现SG[i]还不能大于(不大于k的最大的2的倍数)

所以到这里，做法就有了，对于s串种每一位为1的位置i(从1开始计数)
SG^=min(1<<__builtin_ctz(i),1<<(31-__builtin_clz(k)));

最后判断SG是否为0即可。