P3917 异或序列
题目链接
按位考虑,计算有多少个区间异或值使得该位为1,因为该位为1才有贡献。
对每一位异或前缀,记录1,0的个数,易知最终结果是01的个数相乘。
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];} ll ans = 0;for (int i = 0; i < 30; i++) {int cnt[2]{1, 0}; //单独的1也有贡献,所以0的个数初始化为1int x = 0;for (int j = 0; j < n; j++) {x ^= a[j] >> i & 1;cnt[x]++;}ans += 1LL * cnt[0] * cnt[1] * (1 << i);}cout << ans << "\n";return 0;
}