1.必胜必败态介绍#

假设存在一个游戏，游戏双方通过一定相同的策略进行游戏（假设都选择最优策略），直到一方无法进行游戏时被判定为失败。例如：有一堆硬币m个，两个游戏者tom和bob轮流从中取出ai个硬币，共有n个ai。

m = 21,n = 3
a = {1, 3 ,5}

这类游戏存在必败状态和必胜状态，必败状态是指不管在当前状态下游戏者如何选择策略，都必然在对手选择最优策略时候会输。必胜状态为在当前状态下游戏者一定有一种策略将下一轮游戏状态变成必败状态。
如上所示的游戏中，1,3,5都是必胜状态，因为假设当前轮到tom取硬币，状态为5个硬币，则tom可以一次取走5个硬币，bob就输了，所以tom的当前状态可以将下一轮游戏转入必败态所以只要tom选取最优策略必然获胜，1、3同理；而2,4都是必败状态，因为假设当前轮到bob取硬币，状态为4个硬币，则bob可以选择取走3枚硬币，进入状态1而tom进入必胜态，bob输。bob如果取走1枚硬币进入状态3而tom又进入必胜态，bob输。bob并没有其它选择可取，所以bob不论选择什么策略都是输。
从上面的例子可以看出这类游戏只有两种状态：必胜态和必败态。必胜态是通过某一种次策略的选取可以使对手到达必败态的状态，必败态是不论在当前状态怎么选择都将使对手进入必胜态的状态。

2.Nim游戏#

假设此时有N堆石子，每堆石子中有ai个石子，tom和bob可以轮流从任意一堆石子中取出一枚以上的石子。取出最后一个石子的游戏者获胜。

n = 2
a = {3, 3}

这个问题看起来比较复杂，状态比较多，需要搜索很多状态的转移是否进入必败态和是进入必胜态。举几个例子：首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3)(1,3)(2,3)（显然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是必败态，所以(0,3)是必胜态（只要找到一个是必败态的子局面就能说明是必胜态）。(1,3)的后继中(1,1)是必败态（因为(1,1)的唯一子局面(0,1)是必胜态），所以(1,3)也是必胜态。同样可以证明(2,3)是必胜态。所以(3,3)的所有子局面都是必胜态，它就是必败态。通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是必败态当且仅当这两堆石子的数目相等”。如果当前状态是3堆或者更多石子就比容易分析了。但是可以通过递归程序计算每个状态的属性，记忆化搜索可以加快效率，但是时间复杂度仍然高达O（a1a2···an）。
更快的计算方法，首先说结论：
对于一个Nim游戏的局面(a1,a2,...,an)，它是必败态当且仅当a1^a2...^{an=0，其中}表示位异或(xor)运算。
对于一个Nim游戏的局面(a1,a2,...,an)，它是必胜态当且仅当a1^a2...^{an！=0，其中}表示位异或(xor)运算。
下面给出证明：
对于某个局面(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^{k)枚硬币）。则我们可以将ai改变成ai'=ai}k，此时a1^a2...^ai'...^an=a1a2^...an^k=0。
对于某个局面(a1,a2,...,an)，若a1^a2...^{an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1}a2^...ai'^...an=0。因为异或运算满足消去率，由a1^a2...^an=a1a2^...ai'^...an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。证毕。

void solve(int A,int N){
  int x = 0;
  for(int i=0;i<N;i++)x^=A[i];
  if (x!=0)cout<<"tom";
  else cout<<"bob";
}