alan23273850 的刷題筆記
d265: 10165 - Stone Game
出處：https://zerojudge.tw/ShowProblem?problemid=d265
提交：https://zerojudge.tw/Submissions?problemid=d265&account=allllllan123456
問題：給你很多堆石頭，每堆有 $P_i\in[1,2\cdot10^9]$ 個石頭。現在 Jack 和 Jim 正在玩撿石頭的遊戲，每人每回合只能選一個堆，取走裡面的至少一顆石頭，至多可以把整堆通通拿光，那拿走最後一顆石頭的人就贏了 (換句話說沒有石頭拿的人就輸了)。由 Jack 先開始，請問當兩人都採取對自己最有利的策略時，誰會贏？
解法：這題是很有名的 Nim Game，有已知判斷方法，只要把每一堆的石頭數量全部 XOR 起來，得到的數值如果不是 0 那麼先手 (Jack) 勝，如果是 0 則後手 (Jim) 勝。
證明：https://gist.github.com/amoshyc/59009070d3807a02b7b5 (這篇寫得很好)
在開始理解證明之前我們先敘述其骨幹。對於遊戲中的每個狀態我們會有一個函數 $f$ 將其映射到一個特徵值，而 $f$ 的某些性質是主導證明走向的重要關鍵。引理一：如果某個狀態 $S$ 的特徵值 $f(S)=0$，那下一位玩家取完石頭之後新狀態 $T$ 的特徵值必定不為零 $f(T)\ne0$。引理二：若某個狀態 $S$ 的特徵值 $f(S)\ne0$，那麼下一位玩家必定存在一種取石頭的方法使新狀態 $T$ 的特徵值 $f(T)=0$。假設我們已經知道完全沒有石頭的狀態的特徵值必為 0，那麼一開始還沒取石頭之前初始特徵值不為 0 的玩家 A，必須想辦法讓取完之後的特徵值變成 0，這樣子下家 B 無論怎麼取石頭都必定會再度讓特徵值回到不是 0 的狀態，如此一來 A 就能永遠在安全 (不可能沒有石頭的) 狀態，最後就會獲勝。如果一開始還沒取石頭之前就已經遇到特徵值為 0 的玩家 A，他/她無論怎麼取石頭都會讓下家 B 遇到的特徵值不為 0，那麼 B 就擁有主導權，最後就會獲勝。因此我們只要觀察初始狀態的特徵值是否為 0 就能知道誰獲勝。
已知 $f$ 是把每一堆石頭的數量全部 XOR 起來的一個運算，現在就讓我們來證明那兩個引理。引理一的狀態 $S$ 會讓 $f(S)=0$，這意味著假設我現在要取第 $k$ 堆的石頭，那麼其他 $n-1$ 堆的石頭 XOR 起來的數值必定等於第 $k$ 堆石頭的數量，等到石頭取完之後第 $k$ 堆石頭的數量改變了，可是其他堆的石頭數量仍然不變，那麼兩者 XOR 起來的結果 $f(T)$ 就不能為 0 了。引理二的狀態 $S$ 會讓 $f(S)\ne0$，假設 $f(S)$ 的最高位 (MSB) 為第 i 個 bit，那麼必定也存在某第 k 堆的石頭數量 $x[k]$ 的同樣第 i 個 bit 也是 1 (因為如果每一堆石頭數量的第 i 個 bit 都是 0，全部 XOR 起來也會是 0 便不可能是 $f(S)$ 的最高位)，如果玩家決定取這第 k 堆石頭並且使數量變更為 $x[k]\oplus f(S)$，那根據 XOR 的特性 $x[k] \gt x[k]\oplus f(S) \ge 0$，所以是可行的操作，而且最後 $f(T) = f(S)\oplus f(S) = 0$ 也能達到我們的目的。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int N;
6 while (cin >> N && N) {
7 int t, ans = 0;
8 while (N--)
9 cin >> t, ans ^= t;
10 cout << (ans ? "Yes\n" : "No\n");
11 }
12 return 0;
13}