一点一点前进...

0%

欧拉项目 | 301题 | Nim游戏

发表于 分类于 ， Disqus：

题目链接

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

假设有三堆石子，每堆有n1 n2 n3个，有一个函数，X(n1, n2, n3)。如果返回0，说明双方都在最佳移动的情况下，当前手的人必输。否则，返回非零值。

比如X(1, 2, 3)，对于当前手就返回0，不过你怎么拿，对手都能使得其中两堆个数一样，之后他模仿你的操作使得两堆个数一样成立直到0，然后轮到他拿走剩余的一堆，你输了。

题目要求 n ≤ 2 ^ 30时，求X(n,2n,3n) = 0的个数。

n为什么的时候，X(n,2n,3n) = 0成立呢？

我们定义定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。更严谨的定义是：

  1. 无法进行任何移动的局面（也就是terminal position）是P-position；
  2. 可以移动到P-position的局面是N-position；
  3. 所有移动都导致N-position的局面是P-position。

(Bouton’s Theorem)对于一个Nim游戏的局面(a1,a2,…,an)，它是P-position当且仅当a1^a2^…^an=0，其中^表示异或(xor)运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按照两种position的证明来的。

根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题：

  1. 这个判断将所有terminal position判为P-position；
  2. 根据这个判断被判为N-position的局面一定可以移动到某个P-position；
  3. 根据这个判断被判为P-position的局面无法移动到某个P-position。

第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。
第二个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an<>0，一定存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。不妨设a1^a2^…^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai’=ai^k，此时a1^a2^…^ai’^…^an=a1^a2^…^an^k=0。
第三个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an=0，一定不存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。因为异或运算满足消去率，由a1^a2^…^an=a1^a2^…^ai’^…^an可以得到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。

有了以上的定理，使得X(n,2n,3n) = 0，就是要求n ^ 2n ^ 3n = 0
代码很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

值得说的是，求n2的时候用移位操作会比较快，不过好的编译器可能会*2做优化，不管怎样，自己显式的写出来比较好；求n3的时候用加法会比直接*3快，这一步用乘法的话比用加法慢20%+，加法7s多一点计算完成，而用乘法需要9秒。