题目1：有n堆石子，每堆有$a_i$个石子，规定每个人一次只能从一堆中选出若干个拿走，不可不取，最后取完石子的人胜利，假设每个人都很聪明，求先手必胜还是后手必胜。

我们令$t = a_1 \quad xor \quad a_2 \quad xor \quad a_3 \quad xor ... a_n$，则若$t=0$，则为利他态（用T表示），若$t>0$，为利己态（用S表示）。

定理1: 对于一个S态，在按照题目要求取了某些石子之后，一定能转变成T态。

目前状态是S态，那么t>0。

找出t的二进制表达下最高位是1的是第p位，那么从$a_1, a_2, a_3, ..., a_n$中肯定能够找到一个第p位是1的

那么设找到的数是$a_k$，那么令$a_k = a_k \quad xor \quad t$，显然，$a_k \quad xor \quad t < t$，那么就满足了命题要求，而且操作完成后$t' = 0$

定理2: 对于一个T态，在按照题目要求取了某些石子之后，一定能转变成S态。

定理2的正确性则是显然的。

结论1：任意一个S态，都能通过一次转移到T态；反之亦然。那么如果先手是S态那么就一定能通过定理1的移动获胜。

题目2：有n堆石子，每堆有$a_i$个石子，规定每个人一次只能从一堆中选出若干个拿走，不可不取，最后取完石子的人失败，假设每个人都很聪明，求先手必胜还是后手必胜。

定义状态：当一堆石子中只有一个石子，称为孤单堆；否则称为充裕堆。

在S，T态中，如果充裕堆的个数大于等于2；那么分别记为S2，T2；如果充裕堆的个数等于1，分别记为S1，T1；否则，分别记为S0，T0。

定理3: 对于一个S0态，由于孤单堆个数为奇数，那么必输；对于一个T0态，必赢。

很简单就能证明。

定理4: S1态是必胜态。

前提是方法正确。

如果孤单堆个数是奇数，那么就把充裕堆取完。

如果是偶数，那么把充裕堆取到只有1个石子。

定理5: S2态不能一次转化到T0态，但是只能一次转化到T2态。

显然由定理1，S态一次不会取完整堆，然后变为T态。

所以只能变成T2态。

定理6: T2态只能一次转化到S1，S2态。

很明显，不能一次取两堆。

定理7: S2态是必胜态。

先转化到T2态，T2可以转化到S1，S2态；

如果转化到S2态，继续转化到T2态。

如果转化到S1态，那么必赢。

结论2：必胜态：S1，S2，T0；必败态：T1，T2，S0。

例题：BZOJ 1022

题目摘要：小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有n堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。

【题解】就是题目2，参照结论2即可。

# include <stdio.h>
using namespace std;
int T, n, a[510];
int main() {
	scanf("%d", &T);
	while(T--) {
		int ans = 0;
		scanf("%d", &n);
		for (int i=1; i<=n; ++i) {
			scanf("%d", &a[i]);
			ans = ans ^ a[i];
		}
		bool flag;
		if (ans == 0) {
			flag = 0;
			for (int i=1; i<=n; ++i) 
				if(a[i] != 1) {
					flag = 1;
					break;
				}
		} else {
			flag = 1;
			for (int i=1; i<=n; ++i)
				if(a[i] > 1) {
					flag = 0;
					break;
				}
		}
		if (flag) puts("Brother");
		else puts("John");
	}
}