题解 | #小美的区间异或和#

元素a[i]对最终答案的总贡献为：a[i]在所有包含它的连续子数组中与其他元素构成的所有可能数对(a[i], a[j])的异或和。从0到n-1遍历a[i]，累加每一个a[i]的贡献，就得到最终答案。遍历单个a[i]的所有包含数组需要O(n)，每个数组内部计算数对异或和需要O(n^2)，遍历整个a数组需要O(n)，总复杂度为O(n^4)，显然不行。但是通过对异或计算进行优化，可以将总复杂度降低为O(n) * O(log(max(a[i])))，满足题目要求。

对异或和的计算进行优化：注意到计算异或和时每一个二进制位是独立的，而每一位的值只有0和1两种。以第0位为例，考虑数组a中每一位元素的第0个二进制位，形成新数组a0，则"a[i]在所有包含它的连续子数组中与其他元素构成的所有可能数对(a[i], a[j])的异或和" 在第0位中的体现即为 “a0[i]在所有包含它的连续子数组中与其他元素构成的所有可能数对(a0[i], a0[j])的异或和” 。

a0[i]和a0[j]的值无非4种情况：(0,0), (0,1), (1,0), (1,1)，而当a0[i]和a0[j]的值相同时二者的异或值为0，只有二者的值不同时才对结果有贡献。每一个(0,1)或(1,0)数对在第0位的贡献为1，在第b位的贡献即为1<<b。推导到这里就已经基本解决了，想办法压缩计算第b位总贡献的复杂度就行了。

对a0[i]，考虑所有包含当前位置i的可能区间[l, r]，区间左端点 l 的可能值为[0,i]共i+1种，区间右端点 r 的可能值为[i,n]共n-i种。如果当前元素a0[i]=0，考虑它左侧的所有a0[j]=1(j<i)，累加所有(j+1)（即包含位置j的区间左端点数）与(n-i)（即位置i往右的所有可能的区间右端点数）的乘积(j+1) * (n-i)就得到了二进制位0的总贡献，(j+1)(n-i) << b 则是二进制位b的总贡献。使用两个变量sum0和sum1分别存储0和1的前缀和，实现O(n)地计算当前位的总贡献。详细步骤见代码注释。

#include <stdio.h>
#include <queue>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <stack>
#define int long long
const int maxn = 1e5 + 9;
const int maxm = 1e5 + 9;
using namespace std;
const int p = 1e9 + 7;

int n;
int a[maxn];


signed main(void)
{
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];

	int ans = 0;

	for (int b = 0; b < 32; b++) { // 独立考虑每一位的异或
		int mask = 1 << b;
		int sum0 = 0, sum1 = 0;
		int tmp_ans = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] & mask) {
				tmp_ans += sum0 * (n - i); // n-i: 能够使数组[l, r]包含a[i]的所有可能的右端点 r 的数量 (l<r)
				sum1 += (i + 1); // i+1: 能够使数组[l, r]包含a[i]的所有可能的左端点 l 的数量
				// 二者相乘表示元素a[i]在b位的总贡献，即所有包含a[i]的连续子数组中，满足b位为(0,1)或(1,0)的数对的总数量。
			}
			else {
				tmp_ans += sum1 * (n - i);
				sum0 += (i + 1);
			}
			tmp_ans %= p;
			sum0 %= p;
			sum1 %= p;
		}
		ans = (ans + (tmp_ans << b) % p) % p;
	}

	cout << ans;



	return 0;
}