1.必勝必?cái)B(tài)介紹#
假設(shè)存在一個(gè)游戲筹淫，游戲雙方通過一定相同的策略進(jìn)行游戲（假設(shè)都選擇最優(yōu)策略）撬槽，直到一方無法進(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并沒有其它選擇可取，所以bob不論選擇什么策略都是輸容燕。
從上面的例子可以看出這類游戲只有兩種狀態(tài)：必勝態(tài)和必?cái)B(tài)梁呈。必勝態(tài)是通過某一種次策略的選取可以使對(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è)問題看起來比較復(fù)雜，狀態(tài)比較多颈嚼，需要搜索很多狀態(tài)的轉(zhuǎn)移是否進(jìn)入必?cái)B(tài)和是進(jìn)入必勝態(tài)毛秘。舉幾個(gè)例子：首先(3,3)的子局面（也就是通過合法移動(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)的子局面就能說明是必勝態(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)。通過一點(diǎn)簡(jiǎn)單的數(shù)學(xué)歸納抚官，可以嚴(yán)格的證明“有兩堆石子時(shí)的局面是必?cái)B(tài)當(dāng)且僅當(dāng)這兩堆石子的數(shù)目相等”扬跋。如果當(dāng)前狀態(tài)是3堆或者更多石子就比容易分析了。但是可以通過遞歸程序計(jì)算每個(gè)狀態(tài)的屬性凌节，記憶化搜索可以加快效率钦听，但是時(shí)間復(fù)雜度仍然高達(dá)O（a1a2···an）洒试。
更快的計(jì)算方法，首先說結(jié)論：
對(duì)于一個(gè)Nim游戲的局面(a1,a2,...,an)朴上，它是必?cái)B(tài)當(dāng)且僅當(dāng)a1a2...an=0垒棋，其中表示位異或(xor)運(yùn)算。
對(duì)于一個(gè)Nim游戲的局面(a1,a2,...,an)痪宰，它是必勝態(tài)當(dāng)且僅當(dāng)a1a2...an叼架！=0，其中表示位異或(xor)運(yùn)算衣撬。
下面給出證明：
對(duì)于某個(gè)局面(a1,a2,...,an)乖订，若a1a2...an!=0，一定存在某個(gè)合法的移動(dòng)具练，將ai改變成ai'后滿足a1a2...ai'...an=0乍构。不妨設(shè)a1a2...an=k，則一定存在某個(gè)ai扛点，它的二進(jìn)制表示在k的最高位上是1（否則k的最高位那個(gè)1是怎么得到的）哥遮。這時(shí)aik<ai一定成立（意味著可以取走ai-(aik)枚硬幣）。則我們可以將ai改變成ai'=aik陵究，此時(shí)a1a2...ai'...an=a1a2...an^k=0昔善。
對(duì)于某個(gè)局面(a1,a2,...,an)，若a1a2...an=0畔乙，一定不存在某個(gè)合法的移動(dòng)，將ai改變成ai'后滿足a1a2...ai'...an=0翩概。因?yàn)楫惢蜻\(yùn)算滿足消去率牲距，由a1a2...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";
}
