博弈论基础
这里主要讨论两人博弈的博弈，不讨论前沿的多人博弈。
前置知识：
- 注意，无特殊说明，所有博弈论的题目均已双方会选择最优方案的前提下进行。
（所以据说我们 \(K8He\) 老师想要出一个概率出错的博弈论（
- 平等组合游戏 \(ICG\)：两人轮流操作，限制条件对两人相同，有有限状态集合，有终止状态且可以达到的游戏。
所以说五子棋不算平等组合游戏，因为执黑不等于执白。
而我们的博弈游戏，大多是平等组合游戏。
- 必胜状态 \(N\)，必败状态 \(P\)：
（以下所有都不用英文字母表示状态，答案是我猪脑过载反应不过来）
P-position 表示 previous，代表先手必败，即后手必胜，N-position 表示 next，代表先手必胜，后手必败。
很多博文都用字母表示，需要知道（
先手必胜与先手必败
在博弈论中，往往存在必胜与必败的状态。
例如：有一堆石子，数目为 \(N\)，初音ミク 和 歌爱ユキ 两个人一次只能取 \(1\) 个或者 \(2\) 个或者 \(3\) 个（不能不取），取到最后一个石子的人获胜，初音ミク先手。
在这之中，明显的，如果 \(N=4\) 初音ミク 必败，因为她不能一次取完但是 歌爱ユキ 可以。
因此，\(N=4k,(k\in Z)\) 时，该状态是先手必败状态。
而对于其他的，初音ミク 可以通过取几个石子让 \(N=4k\)，且转化为 歌爱ユキ 先手，所以必胜。
因此我们可以将状态转移构成一个有向无环图，每个状态要么是先手必胜，要么是先手必败，有：
-
终止状态是先手必败状态。
-
如果一个状态只能转移到必胜，这个状态就是必败。
-
如果可以转移到必败，这个状态就是必胜。
（部分边未画出）
nim游戏：
有 \(n\) 堆石子，初音ミク 和 歌爱ユキ 轮流选一堆石子取若干（不可不取），没有石子可取的人失败。
（我觉得看完前置知识可以思考一下所以可以不要往下急着走）
ewq
有点复杂是吧？
一点点来推吧：
最终状态是一个不剩，是必败状态。
-
如果只剩下一堆石子，全拿走可以转换到最终状态（必败状态），所以只剩下一堆石子是必胜状态。
-
如果只剩下两堆石子：
拿 \((3,3)\) 举例子：
（ps：因为只要能转移到必败状态就是必胜状态，所以省去了一下边和点）
从左上到右下解释一下，因为 \((0,0)\) 是先手必败，所以能转移到它的父局面 \((0,1)\) 是先手必胜，只能转移到 \((0,1)\) 的父局面 \((1,1)\) 是先手必败，\((1,3)\) 能够转移到必败的 \((1,1)\) 是先手必胜。
就像 dfs 一样，而存在大量的重合子，可以考虑记忆化搜索。
时间复杂度是 \(O(a_1\cdot a_2 \cdot a_3\cdot …… \cdot a_n)\)。
但是通过一个定理可以让时间复杂度极大地降低。
定理：如果所有石子数量亦或为 \(0\)，先手必败，否则先手必胜。
而证明这个定理就要证明三个小定理：
-
定理 \(1\)：最终状态是必败状态。
-
定理 \(2\)：对于 \(a_1\bigoplus a_2 \bigoplus …\bigoplus a_n \neq 0\) 来说，一定存在某种对策使其等于 \(0\)。
-
定理 \(3\)：对于 \(a_1\bigoplus a_2 \bigoplus …\bigoplus a_n = 0\) 来说，无论如何对策都没有继续等于 \(0\) 的可能。
我们主要来证明难以理解的定理 \(2\)：
设 \(a_1\bigoplus a_2 \bigoplus …\bigoplus a_n=k,(k\in Z,k\neq 0)\)，而其二进制最高位数是 \(d\)。
要让其成为 \(0\)，那么就要让 \(a_i=a_i\bigoplus k\)。
其第 \(d\) 位置上数是 \(1\)，代表着一定有奇数个 \(a_i\) 的第 \(d\) 位置是 \(1\)。
那么一定有 \(a_i \bigoplus k> a_i\)。
具有合法对策。
证毕。
Miku's Code
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
typedef long double llf;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-8;
namespace mystd{
il int Max(int a,int b)<%if(a<b) return b;return a; %>
il int Min(int a,int b)<%if(a>b) return b;return a; %>
il int Abs(int a)<% if(a<0) return a*(-1);return a; %>
il double fMax(double a,double b)<%if(a<b) return b;return a; %>
il double fMin(double a,double b)<%if(a>b) return b;return a; %>
il double fAbs(double a)<% if(a<0) return a*(-1);return a; %>
il int dcmp(double a){
if(a<-eps) return -1;
if(a>eps) return 1;
return 0;
}
}const int maxn=1e4+50;
int T,n,a[maxn];
int mj;
il void clear(){
for(rg i=1;i<=n;++i) a[i]=0;
mj=0;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(rg i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(rg i=1;i<=n;++i) mj=mj^a[i];
if(mj==0) printf("No\n");
else printf("Yes\n");
clear();
}
return 0;
}