0067.异或和之和.md

67. 异或和之和

题目链接

C

C++

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