$Nim$游戲

$n$堆物品，每堆有$a_i$個，每個玩家輪流取走任意一堆的任意個物品，但不能不取，取走最后一個物品的人獲勝。

$Nim$游戲是一種經典的公平組合游戲。現在對它進行分析。

首先定義兩個博弈中的狀態：

• 必勝狀態：先手必勝的狀態。
• 必敗狀態：先手必敗的狀態。

對于這兩個狀態，我們可以知道：

1. 沒有后繼狀態的狀態必然是必敗狀態。在這個狀態中先手的是敗者，因為他無法通過操作將游戲進行下去了。
2. 一個狀態是必勝狀態當且僅當存在至少一個必敗狀態為它的后繼狀態。在這個狀態中先手的人可以通過一次操作讓對手在必敗狀態中先手。
3. 一個狀態的所有后繼狀態均為必勝狀態，那么這個狀態為必敗狀態。在這個狀態中先手，無法避免讓對方在必勝狀態中先手。

回到$Nim$游戲：

在$Nim$游戲中，一個很顯然的必敗狀態就是所有物品堆中物品的數量都為$0$，即$[0,0,...,0]$。這個狀態也是最終態。可以知道，在最終態時，所有物品堆中的物品數量的異或和是等于$0$的，我們不妨假設狀態和物品數量的異或和有關系。

證明有關：

一個非$0$的異或和，產生最高位的$1$總需要有奇數個數字來提供對應位置的$1$。而我們為了消去這個$1$，可以選擇任意一個提供這個$1$的數字，使其二進制中該位上的數字為$0$,而且修改最高位為$0$后得到的數字永遠小于原來的數字，也就是說，我們可以任意修改其他位上的數字從而使得全部物品數量的異或和為$0$。

而對于一個為$0$的異或和，假設存在一個$b\ne a_i$使得我們將$a_i$修改為$b$后，異或和還是為$0$，則有$0\oplus a_i\oplus b=0$，為了使這個式子成立$b$就要等于$a_i$，與假設違背。

換句話說，對于一個物品數量異或和不為$0$的狀態，我們可以通過一次操作將物品數量的異或和修改為$0$，而對于一個物品數量異或和為$0$的操作，我們無法只通過一次操作保持物品數量的異或和不變。

從上可以得出，在$Nim$游戲中，物品數量異或和為$0$的狀態是必敗狀態，物品數量異或和不為$0$的狀態是必勝狀態。

接下來看例題：

【模板】Nim 游戲

【模板】Nim 游戲

題目描述

甲，乙兩個人玩 nim 取石子游戲。

nim 游戲的規則是這樣的：地上有 $n$ 堆石子（每堆石子數量小于 $10^4$），每人每次可從任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能從一堆里取。最后沒石子可取的人就輸了。假如甲是先手，且告訴你這 $n$ 堆石子的數量，他想知道是否存在先手必勝的策略。

輸入格式

本題有多組測試數據。

第一行一個整數 $T$ （$T\le 10$），表示有 $T$ 組數據

接下來每兩行是一組數據，第一行一個整數 $n$，表示有 $n$ 堆石子，$n\le 10^4$。

第二行有 $n$ 個數，表示每一堆石子的數量.

輸出格式

共 $T$ 行，每行表示如果對于這組數據存在先手必勝策略則輸出 Yes，否則輸出 No。

樣例 #1

樣例輸入 #1

2
2
1 1
2
1 0

樣例輸出 #1

No
Yes

---

根據剛才的推論，我們只需要計算所有數字的異或和，就可以得出先手時處在必勝狀態還是必敗狀態。用$O(n)$的復雜度即可得出最后的勝負結果。

#include<bits/stdc++.h>
using namespace std;void solve()
{int n; cin >> n;int ans = 0;for(int i = 1; i <= n; ++i){int x; cin >> x;ans ^= x;}cout << (ans ? "Yes" : "No") << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _; cin >> _;while(_--) solve();return 0;
}