尼姆博弈的实现

尼姆博弈的思想主要体现为：
有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。

计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示这种运算，先看（1，2，3）的按位模2加的结果：

1 =二进制01

2 =二进制10

3 =二进制11 （+）

———————

0 =二进制00 （注意不进位）

对于奇异局势（0，n，n）也一样，结果也是0。

任何奇异局势（a，b，c）都有a（+）b（+）c =0。

注意到异或运算的交换律和结合律，及a（+）a=0，:

a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。

所以从一个非奇异局势向一个奇异局势转换的方式可以是：

1）使 a = c（+）b
2）使 b = a（+）c
3）使 c = a（+）b

分析：NP问题，必胜态N（next player wins）,必败态P(previous player wins)
在必胜态时，无论对方如何将状态调整为必败态，都可以通过一定的处理来减少原有数量来达到必胜态，必胜态的保持会促使游戏的胜利，故游戏的关键就在于是否可以抢夺到必胜态。
假设最后拿到物品的人为胜。

必败局面：也叫奇异局势。无论做出何出操作，最终结果都是输的局面。必败局面经过2次操作后，可以达到另一个必败局面。

必胜局面：经过1次操作后可以达到必败局面。

即当前局面不是必败局面就是必胜局面，而必胜局面可以一步转变成必败局面。

最终状态：
（1）最后剩下一堆物品；（必胜局面）

（2）剩下两堆，每堆一个；（必败局面）

（3）当物品剩下两堆，其中一堆只剩下1颗，另一堆剩下多于n颗物品时，当前取的人只需将多于1颗的那一堆取出n-1颗，则局面变为刚才提到的必败局面。（必胜局面）

下面便是判断是否能获胜的关键：即是否处于奇异局势：
1）将每一组的所有数字按照二进制数表示出来，进行异或，如果异或的结果为零则是必败情况，反之，若不为零，则是必胜情况。
2）在必胜的情况下，由于所有的数进行异或之后是大于零的，那么一定有一个最大的位数和空位取异或后得到该大于零的最大位数（如：两堆物品，去异或后的二进制表示为10，那么，其中大的一定是两位，两个数即为11^1或100），如果想要把必胜转为必败情况，只需要将大的数取一定数量，使最高位相同，且之后的数也具备一定条件，使取异或后的值为零。

分析至此，便可以根据以上的推断已知每堆的数量和堆数来对情况进行推断以及代码实现。

C:
#include <cstdio>
using namespace std;
int main(){
    int m,ans,n;
    while(~scanf("%d",&m)){
        n=ans=0;
        while(m--)
            scanf("%d",&n),ans^=n,printf("ans=%d\n",ans);
        if(ans)printf("Yes\n");
        else printf("No\n");
    }
}