引言

题目链接：https://www.luogu.com.cn/problem/P9236

思路

首先暴力的做法是求出其前缀异或数组 sum， 之后将其两两异或，结果相加，其时间复杂度为 O(n^2)

假设所有 sum 的二进制的第 i 位为 a 个 1 和 b 个 0，那么根据异或的性质，1 和 1，0 和 0 的异或结果为 0，不影响结果。

那么对结果有影响的应该是该位为 0 和该位为 1 的 sum 异或，此时对答案的贡献为 \(2^i\)。

所以该题只需要统计所有 sum 每一位的 0 和 1 的个数 a 和 b，该位对答案的贡献即为 \(2^i * (a * b)\)

代码

#include <bits/stdc++.h>
#define ll long long
#define N 100010

ll a[N],sum[N],w[30][2];

int main() {
	int n;
	std::cin >> n;
	for (int i = 1 ; i <= n ; i ++ ) std::cin >> a[i];

	for (int i = 1 ; i <= n ; i ++ ) sum[i] = sum[i - 1] ^ a[i];

	for (int i = 0 ; i <= n ; i ++ ) {
		for (int j = 0 ; j < 30 ; j ++ ) {
			if(sum[i] >> j & 1) w[j][1] ++ ;
			else w[j][0] ++ ;
		}
	}

	ll ans = 0, pow = 1;
	for (int i = 0 ; i < 30 ; i ++ ) {
		ans += pow * (w[i][0] * w[i][1]);
		pow *= 2;
	}

	std::cout << ans << '\n';

	return 0;
}