算法1

动态规划。

定义f[i][j]表示为以第i个元素为结尾的序列，可以构成为异或和为j的总个数。可以看出，拆分二进制位，每个位进行计算独立，所以依次对每个位进行枚举就好。

时间复杂度O(nlogn)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL a[N];
LL f[N][2];

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    LL res = 0;
    for (int j = 0; j <= 20; ++ j) { //依次枚举每个位
        for (int i = 1; i <= n; ++ i) {
            if (a[i] >> j & 1) {
                f[i][1] = f[i - 1][0] + 1; 
                f[i][0] = f[i - 1][1];
            } else {
                f[i][1] = f[i - 1][1];
                f[i][0] = f[i - 1][0] + 1;
            }
        }
        for (int i = 1; i <= n; ++ i) {
            LL num = 1 << j;
            res += (f[i][1] * num);
        }
    }
    cout << res << endl;
    return 0;
}