根据 Nim\text{Nim}Nim 博弈的性质可知： * 当异或和为 000 时，先手必败。 * 当异或和不为 000 时，先手必胜，只要在某一堆取出一定量的石子使异或和为 000 即可。 记 AAA 数组异或和为 XXX，则答案为 ∑i=1n[X⊕Ai≤Ai]\sum_{i=1}^n [X\oplus A_i\le A_i]∑i=1n [X⊕Ai ≤Ai ]。显然可以 O(N)O(N)O(N) 求出。 当然，如果 X=0X=0X=0，记得特判输出 000。

Nim板子题，不做解释，如有疑问请百度/洛谷题解。 Code:

#include<bits/stdc++.h> #define int long long using namespace std; signed main(){ int n,a[1000010],sum=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; sum^=a[i]; } if(sum==0) cout<<0; else{ int cnt=0; for(int i=0;i<n;i++){ int x=sum^a[i]; if(x<a[i]){ cnt++; } } cout<<cnt; } return 0; }

#include<bits/stdc++.h> #define int long long using namespace std; signed main(){ int n,a[1000010],sum=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; sum^=a[i]; } if(sum==0) cout<<0; else{ int cnt=0; for(int i=0;i<n;i++){ int x=sum^a[i]; if(x<a[i]){ cnt++; } } cout<<cnt; } return 0; }