第十四届蓝桥杯省赛 C/C++ A 组 H 题——异或和之和（AC）-Toy模板网

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯省赛 C/C++ A 组 H 题——异或和之和（AC）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 异或和之和

1.题目描述

给定一个数组 $A_i$ ，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 $\leq L \leq R \leq n$ 的 $L, R$ ，求出数组中第 $L$ 至第 $R$ 个元素的异或和。然后输出每组 $L, R$ 得到的结果加起来的值。

2.输入格式

输入的第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数 $A_i$ ，相邻整数之间使用一个空格分隔。

3.输出格式

输出一行包含一个整数表示答案。

4.样例输入

5
1 2 3 4 5

5.样例输出

6. 数据范围

对于 $30\%$ 的评测用例， $\leq 300$ ；

对于 $60\%$ 的评测用例， $\leq 5000$ ；

对于所有评测用例， $\leq n \leq 10^5$ ， $\leq A_i \leq 2^{20}$ 。

7. 原题链接

异或和之和

2. 解题思路

首先，根据题意进行暴力枚举每个子区间 $[l, r]$ $(1\leq l \leq r \leq n)$ 的异或和，复杂度将是 $O(n^2)$ ，无法通过本题，但可以拿到一定分数。

因为涉及异或运算且观察到 $a_i$ 的取值范围为 $0,2^{20}]$ ，我们不难想到从"拆位"的角度去思考问题。假设对于二进制位的第 $\in[0,20]$ 位，数组中一共有 $x$ 个子区间在该位的异或和为 $1$ ，那么该位对答案的贡献为 $2^{i} \times x$ 。这样我们就将整个大问题，拆成了 $20$ 个子问题，原数组相当于被我们拆分为 $20$ 个 $01$ 数组。

对于每个子问题，也就是对于每个 $01$ 数组，我们需要求出有多少子数组的异或和为 $1$ ，也就是求出前面所说的 $x$ 。这个问题我们可以通过前缀异或来解决。设这里的 $01$ 数组为 $a$ 数组，我们再设一个 $S$ 数组， $S_i$ 表示 $a$ 数组中前 $i$ 个元素的异或和为多少。根据异或运算的性质：

$a_i \oplus a_{i+1} \oplus \cdots \oplus a_{j-1} \oplus a_j=(a_1 \oplus a_2 \oplus \cdots a_j) \oplus (a_1 \oplus a_2 \oplus \cdots \oplus a_{i-1})$

将上述式子用 $S$ 进行代替有：

$a_i \oplus a_{i+1} \oplus \cdots \oplus a_{j-1} \oplus a_j=S_{i-1} \oplus S_j$

如果想使得等式左边等于 $1$ ，即需要满足 $S_{i-1} \ne S_j$ 。

根据上述分析，我们可以枚举每个 $01$ 数组的前缀异或数组 $S$ ，当我们枚举到 $S_j$ 时，我们只需要考虑在它之前有多少个 $S_i$ 和它不同，不同的个数就等于以 $a_j$ 结尾且异或和为 $1$ 的子数组个数，这个统计个数的功能我们可以使用哈希表实现。

这样我们可以在接近 $O (n)$ 的复杂度统计出每个 $01$ 数组子区间异或为 $1$ 的个数，我们设第 $i$ 个二进制位的 $01$ 数组子区间异或为 $1$ 的个数为 $b_i$ ，最终答案为：

$\sum_{i=0}^{20} 2^{i} \times b_i$

时间复杂度： $\times n)$ 。文章来源地址https://www.toymoban.com/news/detail-640318.html

3. AC_Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int a[N][25];
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		for (int j = 0; j <= 20; ++j) {
			a[i][j] = (x >> j) & 1;
			a[i][j] ^= a[i - 1][j];
		}
	}
	LL ans = 0;
	for (int j = 0; j <= 20; ++j) {
		map<int, int> m;
		m[0]++;
		for (int i = 1; i <= n; ++i) {
			int x = m[a[i][j] ^ 1];
			ans += 1LL * (1 << j) * x;
			m[a[i][j]]++;
		}
	}
	cout << ans << '\n';
	return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = 100010;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] a = new int[N][25];
        for (int i = 1; i <= n; ++i) {
            int x = scan.nextInt();
            for (int j = 0; j <= 20; ++j) {
                a[i][j] = (x >> j) & 1;
                a[i][j] ^= a[i - 1][j];
            }
        }
        long ans = 0;
        for (int j = 0; j <= 20; ++j) {
            Map<Integer, Integer> m = new HashMap<>();
            m.put(0, 1);
            for (int i = 1; i <= n; ++i) {
                int x = m.getOrDefault(a[i][j] ^ 1, 0);
                ans += (1L << j) * x;
                m.put(a[i][j], m.getOrDefault(a[i][j], 0) + 1);
            }
        }
        System.out.println(ans);
    }
}

Python

n = int(input())
N = 100010
a = [[0] * 25 for _ in range(N)]
b = list(map(int, input().split()))
for i in range(1, n + 1):
    x = b[i-1]
    for j in range(21, -1, -1):
        a[i][j] = (x >> j) & 1
        a[i][j] ^= a[i - 1][j]
ans = 0
for j in range(21, -1, -1):
    m = {0: 1}
    for i in range(1, n + 1):
        x = m.get(a[i][j] ^ 1, 0)
        ans += (1 << j) * x
        m[a[i][j]] = m.get(a[i][j], 0) + 1
print(ans)