题目链接:link

结论

如果 $ a_1 \oplus a_2 \oplus ... \oplus a_n \not= 0$ ，则先手必胜

证明

1. 操作到最后时，每堆石子数都是\(0\), \(0 \oplus 0 \oplus ... \oplus 0 = 0\)

2. 如果\(a_1 \oplus a_2 \oplus ... \oplus a_n = x \not= 0\),那么肯定可以通过从某一堆中拿走若干颗石子后，将异或结果变成0

   证明：我们先假设 x的最高一位的1在第k位,
   那么在 \(a_1,a_2,...,a_n\) 中，一定存在一个 \(a_i\) ,它的第k位为1，
   \(a_i\oplus x\)一定是小于\(a_i\)的，那么在\(a_i\)中取\(a_i-(a_i\oplus x)\)颗石子，就可以得到\(a_1\oplus a_2 \oplus ...\oplus a_n = 0\),
   因为\(a_i\)中取了\(a_i-(a_i\oplus x)\)颗石子后，就还剩\(a_i-(a_i-(a_i\oplus x))\)颗石子，也就是\(a_i\oplus x\)颗

3. 如果\(a_1\oplus a_2\oplus ...\oplus a_n = 0\),那么无论怎么拿，最终的异或结果一定不为0

   反证法:假设从第i堆石子中拿了若干个,结果仍然为0
   先设第i堆拿完后还剩\({a_i}'\)颗石子,由于不能不拿,所以\(0\lt {a_i}' \lt a_i\),而且\(a_1\oplus a_2\oplus ... \oplus {a_i}' \oplus ...\oplus a_n = 0\),
   那么\((a_1\oplus a_2\oplus ... \oplus a_i \oplus ...\oplus a_n )\oplus (a_1\oplus a_2\oplus ... \oplus {a_i}' \oplus ...\oplus a_n ) = 0\),
   则\({a_i}' \oplus a_i = 0\),也就是\({a_i}'=a_i\),和\(0\lt {a_i}' \lt a_i\)矛盾

那么如果\(a_1 \oplus a_2 \oplus ... \oplus a_n = x \not= 0\),那么先手总可以从某堆拿走若干颗石子，使得\(a_1\oplus a_2\oplus ...\oplus a_n = 0\)，那么最终后手一定没有石子可以拿，则先手必胜
否则，无论先手怎么拿，都会使得\(a_1\oplus a_2\oplus ...\oplus a_n \not= 0\)，那么此时后手就变成了先手，所以最初的先手必败

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,n,ans,x;
    scanf("%d",&k);
    while (k--)
    {
    	ans=0;
    	scanf("%d",&n);
	    while (n--)
	    {
	        scanf("%d",&x);
	        ans^=x;
	    }
	    if (ans) puts("Yes");
	    else puts("No");
	}
    return 0;
}