1.必勝必?cái)B(tài)介紹#

假設(shè)存在一個(gè)游戲，游戲雙方通過(guò)一定相同的策略進(jìn)行游戲（假設(shè)都選擇最優(yōu)策略），直到一方無(wú)法進(jìn)行游戲時(shí)被判定為失敗。例如：有一堆硬幣m個(gè)，兩個(gè)游戲者tom和bob輪流從中取出ai個(gè)硬幣，共有n個(gè)ai。

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

這類游戲存在必?cái)顟B(tài)和必勝狀態(tài)，必?cái)顟B(tài)是指不管在當(dāng)前狀態(tài)下游戲者如何選擇策略，都必然在對(duì)手選擇最優(yōu)策略時(shí)候會(huì)輸。必勝狀態(tài)為在當(dāng)前狀態(tài)下游戲者一定有一種策略將下一輪游戲狀態(tài)變成必?cái)顟B(tài)。
如上所示的游戲中，1,3,5都是必勝狀態(tài)，因?yàn)榧僭O(shè)當(dāng)前輪到tom取硬幣，狀態(tài)為5個(gè)硬幣，則tom可以一次取走5個(gè)硬幣，bob就輸了，所以tom的當(dāng)前狀態(tài)可以將下一輪游戲轉(zhuǎn)入必?cái)B(tài)所以只要tom選取最優(yōu)策略必然獲勝，1、3同理；而2,4都是必?cái)顟B(tài)，因?yàn)榧僭O(shè)當(dāng)前輪到bob取硬幣，狀態(tài)為4個(gè)硬幣，則bob可以選擇取走3枚硬幣，進(jìn)入狀態(tài)1而tom進(jìn)入必勝態(tài)，bob輸。bob如果取走1枚硬幣進(jìn)入狀態(tài)3而tom又進(jìn)入必勝態(tài)，bob輸。bob并沒(méi)有其它選擇可取，所以bob不論選擇什么策略都是輸。
從上面的例子可以看出這類游戲只有兩種狀態(tài)：必勝態(tài)和必?cái)B(tài)。必勝態(tài)是通過(guò)某一種次策略的選取可以使對(duì)手到達(dá)必?cái)B(tài)的狀態(tài)，必?cái)B(tài)是不論在當(dāng)前狀態(tài)怎么選擇都將使對(duì)手進(jìn)入必勝態(tài)的狀態(tài)。

2.Nim游戲#

假設(shè)此時(shí)有N堆石子，每堆石子中有ai個(gè)石子，tom和bob可以輪流從任意一堆石子中取出一枚以上的石子。取出最后一個(gè)石子的游戲者獲勝。

n = 2
a = {3, 3}

這個(gè)問(wèn)題看起來(lái)比較復(fù)雜，狀態(tài)比較多，需要搜索很多狀態(tài)的轉(zhuǎn)移是否進(jìn)入必?cái)B(tài)和是進(jìn)入必勝態(tài)。舉幾個(gè)例子：首先(3,3)的子局面（也就是通過(guò)合法移動(dòng)可以導(dǎo)致的局面）有(0,3)(1,3)(2,3)（顯然交換石子堆的位置不影響其性質(zhì)，所以把(x,y)和(y,x)看成同一種局面），只需要計(jì)算出這三種局面的性質(zhì)就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)顯然是必?cái)B(tài)，所以(0,3)是必勝態(tài)（只要找到一個(gè)是必?cái)B(tài)的子局面就能說(shuō)明是必勝態(tài)）。(1,3)的后繼中(1,1)是必?cái)B(tài)（因?yàn)?1,1)的唯一子局面(0,1)是必勝態(tài)），所以(1,3)也是必勝態(tài)。同樣可以證明(2,3)是必勝態(tài)。所以(3,3)的所有子局面都是必勝態(tài)，它就是必?cái)B(tài)。通過(guò)一點(diǎn)簡(jiǎn)單的數(shù)學(xué)歸納，可以嚴(yán)格的證明“有兩堆石子時(shí)的局面是必?cái)B(tài)當(dāng)且僅當(dāng)這兩堆石子的數(shù)目相等”。如果當(dāng)前狀態(tài)是3堆或者更多石子就比容易分析了。但是可以通過(guò)遞歸程序計(jì)算每個(gè)狀態(tài)的屬性，記憶化搜索可以加快效率，但是時(shí)間復(fù)雜度仍然高達(dá)O（a1a2···an）。
更快的計(jì)算方法，首先說(shuō)結(jié)論：
對(duì)于一個(gè)Nim游戲的局面(a1,a2,...,an)，它是必?cái)B(tài)當(dāng)且僅當(dāng)a1^a2...^{an=0，其中}表示位異或(xor)運(yùn)算。
對(duì)于一個(gè)Nim游戲的局面(a1,a2,...,an)，它是必勝態(tài)當(dāng)且僅當(dāng)a1^a2...^{an！=0，其中}表示位異或(xor)運(yùn)算。
下面給出證明：
對(duì)于某個(gè)局面(a1,a2,...,an)，若a1^a2...^{an!=0，一定存在某個(gè)合法的移動(dòng)，將ai改變成ai'后滿足a1}a2^...ai'^...an=0。不妨設(shè)a1^a2...^{an=k，則一定存在某個(gè)ai，它的二進(jìn)制表示在k的最高位上是1（否則k的最高位那個(gè)1是怎么得到的）。這時(shí)ai}k<ai一定成立（意味著可以取走ai-(ai^{k)枚硬幣）。則我們可以將ai改變成ai'=ai}k，此時(shí)a1^a2...^ai'...^an=a1a2^...an^k=0。
對(duì)于某個(gè)局面(a1,a2,...,an)，若a1^a2...^{an=0，一定不存在某個(gè)合法的移動(dòng)，將ai改變成ai'后滿足a1}a2^...ai'^...an=0。因?yàn)楫惢蜻\(yùn)算滿足消去率，由a1^a2...^an=a1a2^...ai'^...an可以得到ai=ai'。所以將ai改變成ai'不是一個(gè)合法的移動(dòng)。證畢。

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";
}