今天做https://www.luogu.com.cn/problem/P3917

异或序列

题目描述

给出序列 $A_1,A_2,\cdots,A_N$，求

$\sum_{1\le i\le j\le N} A_i\oplus A_{i+1}\oplus\cdots\oplus A_j$

的值。其中，$\bigoplus$ 表示按位异或。

输入格式

第一行，一个整数 $N$。

第二行，$N$个整数 $A_1,A_2,\cdots,A_N$。

输出格式

一个数，为表达式的值。

样例 #1

样例输入 #1

2
1 2

样例输出 #1

6

提示

• 对于 $60\%$ 的数据，$1 \le N \le 10^3$；
• 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le A_i \le 10^9$。

对于每一位，统计前缀异或和在该位上为0和1的个数，然后计算区间数。具体步骤如下：

• 计算前缀异或和数组 prefixXor。

• 对于每一位（从第0位到第31位），统计前缀异或和在该位上为0和1的个数。

• 计算该位上为1的区间数，并累加到总和中。

cpp
#include <stdio.h>

#define MAXN 100005
#define MAX_BIT 31

int prefixXor[MAXN];

int main() {
    int N;
    scanf("%d", &N);

    // 读取输入并计算前缀异或和
    for (int i = 1; i <= N; i++) {
        int A;
        scanf("%d", &A);
        prefixXor[i] = prefixXor[i-1] ^ A;
    }

    long long totalSum = 0;

    // 对于每一位，统计前缀异或和在该位上为0和1的个数
    for (int bit = 0; bit <= MAX_BIT; bit++) {
        int count0 = 0, count1 = 0;

        // 统计前缀异或和在该位上为0和1的个数
        for (int i = 0; i <= N; i++) {
            if ((prefixXor[i] >> bit) & 1) {
                count1++;
            } else {
                count0++;
            }
        }

        // 计算该位上为1的区间数，并累加到总和中
        totalSum += (long long)count0 * count1 * (1LL << bit);
    }

    printf("%lld\n", totalSum);

    return 0;
}