【洛谷P2197】【模板】nim游戏【博弈论】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P2197
甲，乙两个人玩Nim取石子游戏。
nim游戏的规则是这样的：地上有n堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这n堆石子的数量，他想知道是否存在先手必胜的策略。

---

思路：

$NIM$博弈的模板。
定理：$NIM$博弈中先手必胜，当且仅当$a_1 xor a_2 xor a_3 xor...xor a_n>0$。

设$N=a_1 xor a_2 xor a_3 xor...xor a_n$
因为$a_xgeq0$，所以显然$Ngeq0$
首先，当所有石子全部被取完时，显然有$N=0$。此时先手处于必败态。
如果$N>0$，那么设$N$二进制下从左往右数第一位为1的是第$k$位，那么必然有奇数堆石子的第$k$位为1，设第$i$堆石子的第$k$位为1，那么就从$i$中取出若干石子，使得$a_i$变为$a_i xor N$（显然$a_i xor N<a_i$）。由于数量为奇数，那么取完的必然是先手，此时有$N=0$。
通过数学归纳法可得，$N=0$时先手为必败态，$N>0$时先手为必胜态。

证明过程很粗略而不严谨，大概是这个意思好了$:)$

---

代码：

#include <cstdio>
using namespace std;

int T,n,ans,x;

int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		ans=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			ans^=x;
		}
		if (!ans) printf("No
");
			else printf("Yes
");
	}
	return 0;
}