301. 取石子游戏(Nim)
取石子游戏是用数堆石子进行的游戏，由两名玩家轮流从任意一堆中取走任意数量的石子，直到石子全部取完为止。我们考虑按如下方式进行的三堆经典取石子游戏：
- 游戏开始时有三堆石子
- 每名玩家在轮到自己时从任意一堆中取走任意正数枚石子
- 轮到时已无石子可取的玩家输掉游戏
如果用\((n_1,n_2,n_3)\)表示游戏目前的三堆石子分别有\(n_1,n_2,n_3\)枚，那么有一个简单的函数(你可以查询相关知识或自己推理得出)\(X(n_1,n_2,n_3)\)，其函数值为：
- 零，如果在双方都采取最优策略的情况下即将取石子的玩家最终会输掉游戏；或者
- 非零，如果在双方都采取最优策略的情况下即将取石子的玩家最终会赢得游戏。
例如\(X(1,2,3)=0\)，因为无论当前玩家如何操作，他的对手都能够给他留下两堆同样规模的石子并不断仿照他的操作直到石子全部取完；因此当前玩家必定会输掉游戏。举例来说：
- 当前玩家取完后留下(1,2,1)
- 对手玩家取完后留下(1,0,1)
- 当前玩家取完后留下(0,0,1)
- 对手玩家取完后留下(0,0,0)，对手玩家获胜。
求有多少个正整数\(n\le2^{30}\)使得\(X(n,2n,3n)=0\)。
分析：通过简单网络搜索可知\(Nim\)游戏是一个经典的博弈游戏，这个维基页面对这个游戏的游戏规则和相关数学背景进行了详细说明，简而言之，这个游戏存在一个必胜策略，即先手或后手只要采用这个必胜策略，则必然会获得胜利。这个链接很举例说明了这个必胜策略是什么，即假设有一堆石子，个数分别为\((n_1,n_2,\cdots,n_k)\)，\(XOR\)函数表示异或函数，则有：
- \(XOR(n_1,n_2,\cdots,n_k)=0\)，则后手必胜；
- \(XOR(n_1,n_2,\cdots,n_k)\ne0\)，则先手必胜。
题目中给出的\(X\)函数实际上就是\(XOR\)异或函数，至于为什么可以使用异或函数来判断是否必胜，大家可以参考以上的维基页面，下面我们基于以上结论继续分析。
题目要求使得\(XOR(n,2n,3n)=0,n\le2^{30}\)的正整数的个数。根据二进制运算和异或运算的运算规则，主要有以下几个：
- 归零律\(XOR(a,a)=0\)，即一个数和其自身的异或为零；
- \(SUM(a,b)=XOR(a,b)+AND(a,b)\)，这里的\(SUM\)是普通加法，\(AND\)是与运算；
- 二进制下一个数乘以二，即把这个数的二进制表示左移一位，同时在末尾被零，如数字二的二进制表示为\((10)_2\)，而四的二进制表示为\((100)_2\)。
基于以上规则容易得知如果\(XOR(n,2n,3n)=0\)，则有\(XOR(n,2n)=3n=n+2n\)，即：
根据以上第三条规则，二进制下一个数乘以二即左移一位，并在末尾补零。又根据与运算的运算规则，只有两位同时为\(1\)时结果才会为\(1\)，所以只要一个数的二进制表示中没有连续的\(1\)，则其左移一位后，必然只会有\(1\&0,0\&1,0\&0\)三种情况，它们的结果都是零，所以最终两个数与运算的结果也会是零。所以我们现在的问题转化成，找到\(n\le2^{30}\)范围内其二进制表示中不存在两个连续的\(1\)有数\(n\)的个数。
我们从排列组合角度思考以下问题，即要对一些\(0,1\)进行排列，使得没有两个\(1\)挨在一起，假设对于\(n\)个数的符合要求的方法数为\(f(n)\)，则有：
- 假设一个数，显然符合要求的只有\(1\)这一种，即\(f(1)=1\)；
- 假设有两个数，符合要求的有\(01,10\)两种，即\(f(2)=2\)；
- 对于\(n\)个数，有两种情况，假设最左侧的数为\(1\)，则紧挨着它的右侧的数不能是\(1\)，只能是零，即剩下的\((n-2)\)个数中不能有两个连续的\(1\)；第二种情况是最左侧的数是\(0\)，它的右侧即可以\(0\)也可以是\(1\)，也即剩下\((n-1)\)个数不能有连续的\(1\)。
综上我们有\(f(n)=f(n-1)+f(n-2),where\ f(1)=1,f(2)=2\)，显然这是一个斐波那契数列，只是首项略有不同，而\(f(30)\)即为题目所求。代码就非常简单了，简列如下：
# time cost = 1.51 µs ± 31.6 ns
def main(N=30):
a,b = 1,2
for _ in range(N):
a,b = b,a+b
return a