题意：

三堆石子的数量分别为k，4k，5k，进行Nim博弈，问在k小于$2^n$的时候，有多少种情况先手一定会获得胜利。

思路：

这道题被我打表+OEIS水过了…

之后看了一下正解，是这样子的：

当k^4k^5k==0时，后手赢。

k^4k^5k=0可以化成k^4k=5k，

因为有k+4k=5k，而且4k是k的二进制形式左移两位，

两个数异或与相加的得数不同的情况只有1和1的时候。

所以k和k左移两位的数不能有都是1的某一位，即k的二进制形式每隔两个数不能都是1，比如1010这种是不行的。

那么如何得出递推式呢？

可以这样进行考虑：

设f(n)表示n位长度(总数为$2^{n-1}$)的满足上述条件的k的个数：

对于f(4)来说，肯定要加上f(3)，就相当于指的是最高位为0的所有情况，

因为第二位肯定不能为1，所以就忽略这一位，

然后加上f(2)，这指的是最高三位为100的所有情况，

然后还有可能出现最高三位为110的情况，但是因为这时候第二位也为1了，所以最后一位只能是0。

同理对于f(5)来说，肯定要加上f(4)，然后加上f(2)，表示的是最高三位为100的所有情况，然后还可能出现最高三位为110的情况，因为这时候第二位也为1，那么第四位只能为0，后面一位是随便的（只要内部合法即可），相当于加上f(1)。

同理对于f(6)来说，肯定要加上f(5)，然后加上f(3)，表示的是最高三位为110的所有情况，然后还可能出现最高三位为110的情况，因为这时第二位也为1，那么第四位只能为0，后面两位是随便的（只要这两位内部合法即可），相当于加上f(2)。

所以，f(n)=f(n-1)+f(n-3)+f(n-4)。

之后构造矩阵，快速幂就可算出后手赢的种数，总数减它就是前手赢的种数。