$Nim$游戲

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

$Nim$游戲是一種經(jīng)典的公平組合游戲?，F(xiàn)在對它進(jìn)行分析。

首先定義兩個博弈中的狀態(tài)：

• 必勝狀態(tài)：先手必勝的狀態(tài)。
• 必敗狀態(tài)：先手必敗的狀態(tài)。

對于這兩個狀態(tài)，我們可以知道：

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

回到$Nim$游戲：

在$Nim$游戲中，一個很顯然的必敗狀態(tài)就是所有物品堆中物品的數(shù)量都為$0$，即$[0,0,...,0]$。這個狀態(tài)也是最終態(tài)?？梢灾?#xff0c;在最終態(tài)時，所有物品堆中的物品數(shù)量的異或和是等于$0$的，我們不妨假設(shè)狀態(tài)和物品數(shù)量的異或和有關(guān)系。

證明有關(guān)：

一個非$0$的異或和，產(chǎn)生最高位的$1$總需要有奇數(shù)個數(shù)字來提供對應(yīng)位置的$1$。而我們?yōu)榱讼ミ@個$1$，可以選擇任意一個提供這個$1$的數(shù)字，使其二進(jìn)制中該位上的數(shù)字為$0$,而且修改最高位為$0$后得到的數(shù)字永遠(yuǎn)小于原來的數(shù)字，也就是說，我們可以任意修改其他位上的數(shù)字從而使得全部物品數(shù)量的異或和為$0$。

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

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

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

接下來看例題：

【模板】Nim 游戲

【模板】Nim 游戲

題目描述

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

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

輸入格式

本題有多組測試數(shù)據(jù)。

第一行一個整數(shù) $T$ （$T\le 10$），表示有 $T$ 組數(shù)據(jù)

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

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

輸出格式

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

樣例 #1

樣例輸入 #1

2
2
1 1
2
1 0

樣例輸出 #1

No
Yes

---

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

#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;
}