A. Nim Game Is XOR Game结论一个局面是必败态当且仅当数组中正数的个数不超过1。因此Alice 第一步想保证胜利就必须把局面变成“至多一个正数”的状态。证明如果当前数组中正数个数不超过1则不存在非零数组b满足0 b_i a_ib_1 xor b_2 xor ... xor b_n 0b不全为零因为只有一个正数位置时异或值不可能为0没有正数时更不能操作。所以这是必败态。如果当前数组中至少有两个正数记所有数的异或和为s。若s 0直接取b a可以把数组变成全0。若s ! 0按照经典 Nim 的性质存在某个位置i满足(s xor a_i) a_i。令b_i s xor a_i其余位置b_j a_j则b的异或和为0并且操作后只剩第i个位置为正数。所以任意至少两个正数的局面都是必胜态。计数设初始数组异或和为s。我们要数有多少种合法的b使得操作后的数组c a - b是必败态。变成全0这要求b a合法当且仅当s 0贡献1。只剩一个正数假设操作后只剩位置i为正数即c_i 0 c_j 0 (j ! i)则b_j a_j (j ! i) b_i a_i - c_i要求xor(b) 0s xor a_i xor b_i 0所以b_i s xor a_i为了让c_i a_i - b_i 0必须满足(s xor a_i) a_i每个满足条件的位置i恰好对应一种合法选择。特别地当n 1时Alice 没有任何合法操作答案恒为0。算法对每个测试用例读入数组并求异或和s。如果n 1输出0。如果s 0答案为1。否则统计满足(s xor a_i) a_i的位置个数。复杂度每个测试用例时间复杂度O(n)总复杂度O(sum n)。空间复杂度O(n)也可以改成边读边存较少信息但当前限制下足够。参考代码#includebits/stdc.husingnamespacestd;staticconstlonglongMOD998244353;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cint;while(t--){intn;cinn;vectorinta(n);intxr0;for(inti0;in;i){cina[i];xr^a[i];}if(n1){cout0\n;continue;}longlongans0;if(xr0){ans1;}else{for(intx:a){if((xr^x)x){ans;}}}coutans%MOD\n;}return0;}