Nim博弈簡介

題面

洛谷P2197

有 n n n堆石子（ n n n > > > 0 0 0），每一堆有 a i a_i ai?（ a i a_i ai? > > > 0 0 0, 1 1 1 < = <= <= i i i < = <= <= n n n）個石子，
每人每次可以從任意一堆石子里，取出任意多枚石子扔掉，可以取完，不能不取，每次只能從一堆里取，最后沒有石子可以取的人輸掉這場游戲，
設甲為先手，乙為后手，兩個人以最佳策略進行操作，
給出 n n n，和這 n n n堆石子分別的數量，請問是否存在先手必勝的策略？

結論

如果這n堆石子的數量滿足：
a 1 a_1 a1? x o r xor xor a 2 a_2 a2? x o r xor xor a 3 a_3 a3? x o r xor xor . . . ... ... x o r xor xor a n a_n an? = = = 0 0 0
則先手必敗，否則先手必勝，

理解

要理解結論的式子，就要理解為什么使用異或，以及異或為0的意義，這兩點將在接下來的理解中提到，

1.終結狀態 和 異或

那么我們首先來看該問題的“終結點”（Terminal Position）是什么，

顯然，當游戲結束的時候，場面上的情況為一粒石子都不剩，即：
a 1 a_1 a1? = = = a 2 a_2 a2? = = = a 3 a_3 a3? = = = . . . ... ... = = = a n a_n an? = = = 0 0 0
此時，顯然有它們的異或和為0，即：
a 1 a_1 a1? x o r xor xor a 2 a_2 a2? x o r xor xor a 3 a_3 a3? x o r xor xor . . . ... ... x o r xor xor a n a_n an? = = = 0 0 0

而我們還知道一個特點，對一堆石子 a i a_i ai?操作，將其變為一個數 n e w a i newa_i newai?（當然，因為是拿出至少1個石子，所以 n e w a i newa_i newai?小于 a i a_i ai?），其實等價于對 a i a_i ai?異或一個數字 x x x，來使得 a i a_i ai? x o r xor xor x x x = = = n e w a a newa_a newaa?.

因此我們可以得出第一個特性：玩家對某一堆石子的操作實際上等同于對該堆石子的異或，
用人話講就是，你對 a i a_i ai?操作一次相當于把 a i a_i ai?變成了 n e w a i newa_i newai?，只不過可以通過異或運算來達到目的，
就這么簡單，

2.玩家的操作 與 異或

然后我們可以看一看玩家的每一次操作對所有石子數量的異或和產生了什么影響，

顯然，如果當前狀況是
a 1 a_1 a1? x o r xor xor a 2 a_2 a2? x o r xor xor a 3 a_3 a3? x o r xor xor . . . ... ... x o r xor xor a n a_n an? = = = 0 0 0
那么，上一個狀況的時候，一定有異或和不為0，即：
a 1 a_1 a1? x o r xor xor a 2 a_2 a2? x o r xor xor a 3 a_3 a3? x o r xor xor . . . ... ... x o r xor xor a n a_n an? = = = k k k( k k k != 0)
原因是，這次操作一定會改變一個數 a i a_i ai?，且只改變 a i a_i ai?，
而現在， a i a_i ai?與“其他數字的異或和”（注意斷句）的異或結果為 k k k，如果把“其他數字的異或和”設為 x x x，那么現在的 a i a_i ai?與 x x x相等，
但是操作之前的 a i a_i ai?與 x x x不同，因此他們的異或結果 k k k不等于0，
由異或運算的結合律，上一個狀況的時候，所有數字的異或結果不為0，

這個時候我們就發現了，既然第1部分中提到，對 a i a_i ai?的操作就是對 a i a_i ai?異或一次，那么根據異或運算的結合律，我們對 a i a_i ai?的一次異或其實就是對總體結果（所有數字的異或和）的一次異或，

OK，那么我們就把整個游戲抽象為了一個異或運算的游戲：
保持原先的規則不變，我們的每次操作都可以讓異或和改變，最后不能再操作的人將輸掉游戲，
誒，這個時候就有同學要問了：異或和為0不能代表游戲結束啊，也不代表所有數都是0啊，
不著急，你現在一定已經有了一點感覺，但是還有一層窗戶紙沒有捅破，
下一節我會向各位同學解釋如何使用異或和這個東西，并且如何利用異或運算在游戲規則內進行操作，

3.如何使用異或

那么我們假設一個一般的狀態：
此時游戲進行到了某個階段，場上的局面是這樣的：
a 1 a_1 a1? x o r xor xor a 2 a_2 a2? x o r xor xor a 3 a_3 a3? x o r xor xor . . . ... ... x o r xor xor a n a_n an? = = = k k k
這里的k可沒有限制啊，可以等于0的，所以我們分情況討論，
假設此時我是先手，你是后手，

①k不等于0的情況：

我們知道所有的數字異或的和為 k k k， k k k不等于0，設 k k k的二進制有 i i i位，那么顯然 k k k的最高位即 i i i位是1，
所以 a 1 a_1 a1?到 a n a_n an?中一定有奇數個數字的第 i i i位為1（不然k的最高位怎么異或出來的是吧），
不理解沒關系，下面有個例子，
【比如，二進制情況下： 11001 x o r 10011 = 1010 11001 xor 10011 = 1010 11001xor10011=1010
1010當中的最高位1就是來自11001的第4位的1，一共有一個數的第4位為1】

理解了這一點，我們就可以想出一個騷操作：你不是異或得到 k k k嗎，我的目標是讓你面對的所有數字都變成0，自然，異或和也就是0了，那么我就要想辦法減少你的某一個數字（拿走某一堆中的一些石子），

所以，怎么減少呢：我們發現，如果讓所有數字的異或和再異或它的結果 k k k，就可以讓它變成0，
而從第2部分中提到的異或的結合律當中，我們可以發現，對異或和異或其實可以用結合律變成對其中的一個數異或，

那么我們要異或誰呢？啊，之前不是提到了那奇數個第 i i i位（ i i i是k的位數）為1的數嗎，就選你們當中的一個了，
為啥呢，因為異或運算的一個性質，馬上就講，

設 a j a_j aj?第 i i i位為1，那么 a j a_j aj? x o r xor xor k k k = = = n e w a j newa_j newaj?
n e w a j newa_j newaj?一定是小于 a j a_j aj?的，因為 k k k的最高位即第 i i i位也是1，因此對 a j a_j aj?異或 k k k之后， n e w a j newa_j newaj?當中高于第 i i i位的那些數字（即第 i i i位左側的那些數字）不會被異或 k k k影響到，而第 i i i位直接變成0，小于第 i i i位的無論如何變化都不會影響第 i i i位已經變成0的事實，
也就是 n e w a j newa_j newaj?的第 i i i位是0，而 a j a_j aj?的第 i i i位是1，且更高位相同，因此 n e w a j newa_j newaj?一定小于 a j a_j aj?，
【比如，11000 xor 1111 = 10111，而10111<11000】

很好，異或完畢之后我們就發現這樣兩件事：
（為了避免影響觀看體驗，我將xor替換為了^，C++的異或運算子）
a 1 a_1 a1? ^ a 2 a_2 a2? ^ a 3 a_3 a3? ^ . . . ... ... ^ a n a_n an? ^ k k k
= = = k k k ^ k k k
= = = 0 0 0
而且
a 1 a_1 a1? ^ a 2 a_2 a2? ^ a 3 a_3 a3? ^ . . . ... ... ^ a n a_n an? ^ k k k
= = = a 1 a_1 a1? ^ a 2 a_2 a2? ^ . . . ... ... ^ ( a j (a_j (aj? ^ k ) k) k) ^ . . . ... ... ^ a n a_n an?
= = = a 1 a_1 a1? ^ a 2 a_2 a2? ^ . . . ... ... ^ n e w a j newa_j newaj? ^ . . . ... ... ^ a n a_n an?
這樣，我的異或操作就是符合游戲規則的（因為你確實拿走了一些石子，減少了某一堆石子的個數）

這個時候輪到你了，你的任何操作，無論異或任何的非零正整數，都會使得異或和即 a 1 a_1 a1? ^ a 2 a_2 a2? ^ a 3 a_3 a3? ^ . . . ... ... ^ a n a_n an?的結果從0變成非零的 n e w k newk newk
而我只需要重復上面的操作，只不過把 k k k變為 n e w k newk newk，然后重新尋找 a j a_j aj?而已，因為我們的操作一定是減少有限的石子總數的，而且我面對的永遠是 a 1 a_1 a1? ^ a 2 a_2 a2? ^ a 3 a_3 a3? ^ . . . ... ... ^ a n a_n an?不為0的狀況，你面對的永遠是 a 1 a_1 a1? ^ a 2 a_2 a2? ^ a 3 a_3 a3? ^ . . . ... ... ^ a n a_n an?等于0的狀況，所以一定在某次操作之后，你發現的異或和為0的狀況是由于所有石子都被我拿完了而導致的，此時你將會輸掉游戲，

發現了嗎，k不為0的時候我是穩贏的，因為我的每一步都會使得你面對一個 a 1 a_1 a1? ^ a 2 a_2 a2? ^ a 3 a_3 a3? ^ . . . ... ... ^ a n a_n an?等于0的狀況，且我們一直在減少石子總量，所以石子總量為0的狀況一定出現在你的回合，

而我是先手，所以k不為0時先手必勝，

②k等于0的情況：

風水輪流轉，這個時候我發現壞了，我的任何操作都會導致異或和不為0，而你可以用①中的操作不斷逼迫我，直到我無路可走，

而我是先手，所以k為0時先手必敗，

注：因為題意中提到了：雙方，也就是你和我，都是絕頂聰明的，使用最佳策略，所以不存在失誤，任何一個先手必勝的情況下都會導致先手必勝的結局，

代碼

#include<iostream>
using namespace std;

int t;

int main()
{
	cin >> t;
	while(t--)//t組測驗資料
	{
		int n, x, k = 0;//初始化異或和k為0，因為任何數異或0都是它本身
		cin >> n;
		for(int i = 1; i <= n; ++i)
			cin >> x, k ^= x;//讀入每一堆石子的同時就求出了異或和k
		cout << (k ? "Yes" : "No") << endl;
		//如果異或和k不為0則先手必勝，否則先手必敗
	}
	return 0;
}

致謝

非常感謝各位閱讀我的博客，也希望自己的一點拙見能夠幫到各位，

轉載請標注轉自千寒的CSDN博客，謝謝！