0067.异或和之和.md

67. 异或和之和

题目链接

C

C++

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] ^= a[i-1];
    }

    ll ans = 0;
    vector<int> c(2);
    rep(b, 21) {
        c[0] = c[1] = 0;
        ll now = 0;
        rep(i, n+1) {
            c[a[i]>>b&1]++;
            ans += 1ll*c[a[i]>>b&1^1]<<b;
        }
    }

    cout << ans << '\n';

    return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = 100010;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] a = new int[N][25];
        for (int i = 1; i <= n; ++i) {
            int x = scan.nextInt();
            for (int j = 0; j <= 20; ++j) {
                a[i][j] = (x >> j) & 1;
                a[i][j] ^= a[i - 1][j];
            }
        }
        long ans = 0;
        for (int j = 0; j <= 20; ++j) {
            Map<Integer, Integer> m = new HashMap<>();
            m.put(0, 1);
            for (int i = 1; i <= n; ++i) {
                int x = m.getOrDefault(a[i][j] ^ 1, 0);
                ans += (1L << j) * x;
                m.put(a[i][j], m.getOrDefault(a[i][j], 0) + 1);
            }
        }
        System.out.println(ans);
    }
}

Python

N = int(input())
nums = [int(i) for i in input().split()]
n = len(nums)
xor_sum = 0
for i in range(n):
  # 子段的异或和
  segment_xor = 0 
  for j in range(i, n):
      # i到j的异或和 = i到j-1的异或和 XOR j
      segment_xor ^= nums[j]
      xor_sum += segment_xor
print(xor_sum)

JS

Go