取石子游戏是用数堆石子进行的游戏，两名玩家轮流从其中一堆中取走一定数量的石子，直到石子全部取完为止。

考虑以下经典规则：游戏开始时有三堆石子，每名玩家在轮到自己时可以从任选一堆并从其中取走任意正数枚石子。已无石子可取的玩家输掉游戏。

若用$(n_1,n_2,n_3)$表示目前三堆石子分别有$n_1, n_2, n_3$枚，可以验证，取决于这三者的值，或者当前玩家必胜，或者其必败（也就是先后手中总有一方有必胜策略）。

用$X(n_1,n_2,n_3)$表示对应的结局，$X(n_1,n_2,n_3)=0$表示当前玩家必败，$X(n_1,n_2,n_3)=1$表示当前玩家必胜。

例如$X(1,2,3)=0$，这是因为无论当前玩家如何操作，其对手总能给他留下两堆同样规模的石子，之后不断仿照其操作即可获胜。

能使$X(n,2n,3n)=0$且不超过$2^{30}$的正整数n共有多少个？

本题难度:

解答

X的值称为Nim-Value，在本题的设定下有当且仅当$n_1,n_2,n_3$的异或值为$0$时$X(n_1,n_2,n_3)=0$，亦即$n_1$异或$n_2$等于$n_3$。

由于$n+2n=3n$，因此仅当$n$和$2n$的二进制表示中没有重合的1时（即加法中无进位）两者的异或值才会等于$3n$，不难看出这等同于n的二进制表示中不存在连续的1。

记$a_d$为不超过d位的二进制数中满足要求的数的数量，则有$a_1=2$， $a_2=3$，以及$a_d=a_{d-1}+a_{d-2}$（分别考虑首位为0和首位为1的情况），因此当时就是斐波那契数列中的一项，查表可得结果$a_{31}=2178309$（计数时尽管$2^d$超过d位，但恰好与多计入的$0$抵消）。

本题无需编程。