思路：拆位

这里下标从 $0$ 开始。

首先考虑两个元素对 $a_i,a_j(i<j)$，在 $(i+1)\times (n-j)$ 个子数组中有贡献，最终我们是将所有异或和都加起来。

我们对于两个数异或值的每个二进制位单独来考虑。

枚举 $a_i$，对于 $a_i$ 的第 $k$ 个二进制位，对于答案有贡献，必然是 $a_j$ 的第 $k$ 个二进制位与其异或值为 $1$ ，那么就是 a(i,k)=0,a(j,k)=1 或者 a(i,k)=1,a(j,k)=0 的情况 。

以 a(i,k)=0 为例，我们需要知道后续所有 a(j,k)=1 的 $a_j$ 与 $a_i$ 构成的子数组的数量。第 $k$ 位对答案的贡献为 $2^k$ 。那么就是 $(i+1)\times (n-j)$ ，所以对于第 $k$ 个二进制位为 $1$ 的 $a_j$ ，其可以把 $n-j$ 存下来。

最后枚举到 $a_i$ 时，贡献即为：$2^k\times (i+1)\times \sum\limits_{j=i+1,a(j,k)=1}^{n-1} (n-j)$ 。

时间复杂度：$O(30n)$

代码

c++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int mod = 1e9 + 7;

    int n;
    cin >> n;

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

    int ans = 0;
    // 考虑每一位
    for (int j = 29; j >= 0; --j) {
        int cnt[2] = {0, 0};
        int v = 1 << j;
        for (int i = n - 1; i >= 0; --i) {
            int b = a[i] >> j & 1;
            ans += 1ll * cnt[!b] * (i + 1) % mod * v % mod;
            ans %= mod;

            cnt[b] += n - i;
            cnt[b] %= mod;
        }
    }

    cout << ans << '\n';

    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final int MOD = 1000000007;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
        }
        long ans = 0;
        for (int j = 31; j >= 0; --j) {
            int[] cnt = new int[2];
            int v = 1 << j;
            for (int i = n - 1; i >= 0; --i) {
                int b = (a[i] >> j) & 1;
                ans += (1L * cnt[1 - b] * (i + 1) % MOD * v % MOD) % MOD;
                ans %= MOD;
                cnt[b] += n - i;
                cnt[b] %= MOD;
            }
        }
        System.out.println(ans);
    }
}

Python

n = int(input())
nums = [int(item) for item in input().split()]
res = 0
mod = 1e9 + 7
for j in range(29, -1, -1):
    cnt = [0, 0]
    v = 1 << j
    for i in range(n - 1, -1, -1):
        b = nums[i] >> j & 1
        res += cnt[~b] * (i + 1) % mod * v % mod
        res %= mod
        cnt[b] += n - i
        cnt[b] %= mod
print(int(res))

题目描述

小美有一个长度为 $n$ 的数组 $a$ 。

他对一个数组的权值定义为，这个数组中两个不同的不同下标 $i,j(0\leq i<j<n)$ ，所有 $a_i\ xor\ a_j$ 的和。
即 $\sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1} a_i\ xor\ a_j$ 。

现在小美想要问你，这个数组的所有连续子数组的权值之和是多少。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示数组的长度。
第二行，$n$ 个整数，第 $i$ 个整数为 $a_i(1 \leq a_i \leq 10^9)$ 。

输出描述

一个整数，表示所有子数组的权值之和，答案对 $10^9+7$ 取模

样例

输入

3
1 2 3

输出

10

说明

对于子数组 $a[1,2]$ 来说，权值为 $3$
对于子数组 $a[2,3]$ 来说，权值为 $1$
对于子数组 $a[1,2,3]$ 来说，权值为 $6$
$3+1=6=10$