1.必勝必敗態(tài)介紹#
假設存在一個游戲，游戲雙方通過一定相同的策略進行游戲（假設都選擇最優(yōu)策略），直到一方無法進行游戲時被判定為失敗。例如：有一堆硬幣m個，兩個游戲者tom和bob輪流從中取出ai個硬幣，共有n個ai。
m = 21,n = 3
a = {1, 3 ,5}
這類游戲存在必敗狀態(tài)和必勝狀態(tài)，必敗狀態(tài)是指不管在當前狀態(tài)下游戲者如何選擇策略，都必然在對手選擇最優(yōu)策略時候會輸。必勝狀態(tài)為在當前狀態(tài)下游戲者一定有一種策略將下一輪游戲狀態(tài)變成必敗狀態(tài)。
如上所示的游戲中，1,3,5都是必勝狀態(tài)，因為假設當前輪到tom取硬幣，狀態(tài)為5個硬幣，則tom可以一次取走5個硬幣，bob就輸了，所以tom的當前狀態(tài)可以將下一輪游戲轉(zhuǎn)入必敗態(tài)所以只要tom選取最優(yōu)策略必然獲勝，1、3同理；而2,4都是必敗狀態(tài)，因為假設當前輪到bob取硬幣，狀態(tài)為4個硬幣，則bob可以選擇取走3枚硬幣，進入狀態(tài)1而tom進入必勝態(tài)，bob輸。bob如果取走1枚硬幣進入狀態(tài)3而tom又進入必勝態(tài)，bob輸。bob并沒有其它選擇可取，所以bob不論選擇什么策略都是輸。
從上面的例子可以看出這類游戲只有兩種狀態(tài)：必勝態(tài)和必敗態(tài)。必勝態(tài)是通過某一種次策略的選取可以使對手到達必敗態(tài)的狀態(tài)，必敗態(tài)是不論在當前狀態(tài)怎么選擇都將使對手進入必勝態(tài)的狀態(tài)。
2.Nim游戲#
假設此時有N堆石子，每堆石子中有ai個石子，tom和bob可以輪流從任意一堆石子中取出一枚以上的石子。取出最后一個石子的游戲者獲勝。
n = 2
a = {3, 3}
這個問題看起來比較復雜，狀態(tài)比較多，需要搜索很多狀態(tài)的轉(zhuǎn)移是否進入必敗態(tài)和是進入必勝態(tài)。舉幾個例子：首先(3,3)的子局面（也就是通過合法移動可以導致的局面）有(0,3)(1,3)(2,3)（顯然交換石子堆的位置不影響其性質(zhì)，所以把(x,y)和(y,x)看成同一種局面），只需要計算出這三種局面的性質(zhì)就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)顯然是必敗態(tài)，所以(0,3)是必勝態(tài)（只要找到一個是必敗態(tài)的子局面就能說明是必勝態(tài)）。(1,3)的后繼中(1,1)是必敗態(tài)（因為(1,1)的唯一子局面(0,1)是必勝態(tài)），所以(1,3)也是必勝態(tài)。同樣可以證明(2,3)是必勝態(tài)。所以(3,3)的所有子局面都是必勝態(tài)，它就是必敗態(tài)。通過一點簡單的數(shù)學歸納，可以嚴格的證明“有兩堆石子時的局面是必敗態(tài)當且僅當這兩堆石子的數(shù)目相等”。如果當前狀態(tài)是3堆或者更多石子就比容易分析了。但是可以通過遞歸程序計算每個狀態(tài)的屬性，記憶化搜索可以加快效率，但是時間復雜度仍然高達O（a1a2···an）。
更快的計算方法，首先說結(jié)論：
對于一個Nim游戲的局面(a1,a2,...,an)，它是必敗態(tài)當且僅當a1a2...an=0，其中表示位異或(xor)運算。
對于一個Nim游戲的局面(a1,a2,...,an)，它是必勝態(tài)當且僅當a1a2...an！=0，其中表示位異或(xor)運算。
下面給出證明：
對于某個局面(a1,a2,...,an)，若a1a2...an!=0，一定存在某個合法的移動，將ai改變成ai'后滿足a1a2...ai'...an=0。不妨設a1a2...an=k，則一定存在某個ai，它的二進制表示在k的最高位上是1（否則k的最高位那個1是怎么得到的）。這時aik<ai一定成立（意味著可以取走ai-(aik)枚硬幣）。則我們可以將ai改變成ai'=aik，此時a1a2...ai'...an=a1a2...an^k=0。
對于某個局面(a1,a2,...,an)，若a1a2...an=0，一定不存在某個合法的移動，將ai改變成ai'后滿足a1a2...ai'...an=0。因為異或運算滿足消去率，由a1a2...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";
}
