301 Nim
通常的 Nim 游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
假设有三堆石子，每堆有 个，有一个函数，。如果返回0，说明双方都在最佳移动的情况下，当前手的人必输。否则，返回非零值。
比如 ，对于当前手就返回 0，不过你怎么拿，对手都能使得其中两堆个数一样，之后他模仿你的操作使得两堆个数一样成立直到 0，然后轮到他拿走剩余的一堆，你输了。
题目要求 时，求 的个数。
值是多少，有 呢？
我们定义 P-position 和 N-position，其中 P 代表 Previous，N 代表 Next。直观的说，上一次移动的人有必胜策略的局面是 P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到移动的人有必胜策略的局面是 N-position，也就是“先手可保证必胜”。更严谨的定义是： 1. 无法进行任何移动的局面（也就是terminal position）是P-position； 2. 可以移动到 P-position 的局面是 N-position； 3. 所有移动都导致 N-position 的局面是 P-position。
Bouton's Theorem 对于一个 Nim 游戏的局面 ，它是 P-position 当且仅当 ，其中 表示异或（xor）运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按照两种 position 进行分类讨论。
根据定义，证明一种判断 position 的性质的方法的正确性，只需证明三个命题： 1. 这个判断将所有 terminal position 判为 P-position； 2. 根据这个判断被判为 N-position 的局面一定可以移动到某个 P-position； 3. 根据这个判断被判为 P-position 的局面无法移动到某个 P-position。
第一个命题显然，terminal position 只有一个，就是全 0，异或仍然是0。
第二个命题，对于某个局面 ，若 ，一定存在某个合法的移动，将 改变成 后满足 。不妨设 ，则一定存在某个 ，它的二进制表示在 的最高位上是 1（否则 的最高位那个 1 是怎么得到的呢？）。这时 一定成立。则我们可以将 改变成 ，此时 。
第三个命题，对于某个局面 ，若 ，一定不存在某个合法的移动，将 改变成 后满足 。因为异或运算满足消去率，由 可以得到 。所以将 改变成 不是一个合法的移动。证毕。
有了以上的定理，使得 ，就是要求 。
代码很简单：
public static int GetAnswer()
{
int count = 0;
long max = 1 << 30;
for (long n = 1; n <= max; n++)
{
long n1 = n;
long n2 = n << 1;
long n3 = n1 + n2;
if ((n1 ^ n2 ^ n3) == 0)
{
count++;
}
}
return count;
}
但是这个题目只需要个数而不需要知道是哪些。仔细考虑 有某种关系，要满足题意的话，二进制需要满足一些条件。不难想到，如果连续两个 1 bits，但前面是一个 0，即连续 3 bits 是 011，那么 是 110， 是 001（进位的 1 最后结果是 0 或者 1 不重要），那么异或肯定不是 0，也就是说，不能有两个连续的 1 bit，或者前面必须还是 1。后者就只有全 1 一种情况了。
所以可以使用两个数组 zeros, ones 来保存可能的数量，一个表示开头是 0 的数的个数，一个表示开始是 1 的数的个数，下标对应的是数的长度。从 1 bit 开始，0 或者 1， 异或都是 0，所以初始时两个数组的第一个元素都是 1。从 到 ，由上面的分析，可以得到如下关系。