A. Nim Game Is XOR Game（Codeforces Round 1105 (Div. 1)）

A. Nim Game Is XOR Game

结论

一个局面是必败态，当且仅当数组中正数的个数不超过1。

因此，Alice 第一步想保证胜利，就必须把局面变成“至多一个正数”的状态。

证明

如果当前数组中正数个数不超过1，则不存在非零数组b满足：

• 0 <= b_i <= a_i
• b_1 xor b_2 xor ... xor b_n = 0
• b不全为零

因为只有一个正数位置时，异或值不可能为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) = 0：

s 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。

算法

对每个测试用例：

1. 读入数组并求异或和s。
2. 如果n = 1，输出0。
3. 如果s = 0，答案为1。
4. 否则统计满足(s xor a_i) < a_i的位置个数。

复杂度

每个测试用例时间复杂度O(n)，总复杂度O(sum n)。

空间复杂度O(n)，也可以改成边读边存较少信息，但当前限制下足够。

参考代码

#include<bits/stdc++.h>usingnamespacestd;staticconstlonglongMOD=998244353;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cin>>t;while(t--){intn;cin>>n;vector<int>a(n);intxr=0;for(inti=0;i<n;++i){cin>>a[i];xr^=a[i];}if(n==1){cout<<0<<'\n';continue;}longlongans=0;if(xr==0){ans=1;}else{for(intx:a){if((xr^x)<x){++ans;}}}cout<<ans%MOD<<'\n';}return0;}