异或和之和

P9236 \[蓝桥杯 2023 省 A\] 异或和之和 - 洛谷 | 计算机科学教育新生态

问题

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1 2	5 1 2 3 4 5

样例输出 #1

1

39

提示

【评测用例规模与约定】

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

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

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

我的解答（未AC）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[100001];
int b[100001] = {0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = b[i - 1] ^ a[i];
        ans += b[i];
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j < i; j++)
        {
            if (b[i] == b[j])
            {
                continue;
            }
            else
            {
                ans += (b[i] ^ b[j]);
            }
        }
    }
    cout << ans << endl;
}

通过异或前缀和数组暴力枚举算出ans，时间复杂度为O（n²），只能拿到60分

优化

要对前缀异或数组中元素两两异或的时间复杂度$O(n^2)$进行优化，考虑到异或的性质，我们可以选择将整数转为二进制，按位运算：

1
2
3
4

for (int j = 0; j <= 20; ++j) {
    a[i][j] = (x >> j) & 1;
    a[i][j] ^= a[i - 1][j];
}

考虑到数字的范围$2^{20}$，我们开a[20]来存每一个元素的每一位；

• a[i][j] = (x >> j) & 1;的作用是求出x二进制的每一位，方法是先右移再和1做位与运算
• a[i][j] ^= a[i - 1][j];即在每一位上求异或前缀和

现在求得了所有元素的异或前缀和数组，这样我们可以在每一位上两两异或并累加求得该位的区间异或和 这里我们使用空间换时间的方式，将$n^2$压缩到$n$：

1
2
3
4
5
6
7
8
9

	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]]++;
		}
	}

这里对代码进行逐行解释：

1

int x = m[a[i][j] ^ 1]

• a[i][j] ^ 1是对该位取反，属于异或运算的基本应用
• 如果异或和区间在该位上的元素（0、1）想对最终结果做出贡献，就必须让$a_i\oplus a_{i+1}\oplus…\oplus a_m$的结果为$1$，在异或前缀和上就是$b_{i-1}\oplus b_{m} $的结果为$1$：由于这里只有$0、1$两个元素，某个元素的异或就是另一个元素，我们使用map（vector[2]同理）来存储0和1的出现次数，以空间换时间;
• x即与a[i][j]异或值为1的元素个数

1
2

ans += 1LL * (1 << j) * x;
m[a[i][j]]++;

• (1 << j) * x;对1左移$j$位再乘上x,即异或前缀和元素在该位上两两异或为1的总次数，并将其还原成十进制计算结果

• m[a[i][j]]++记录该位，用于后续该位元素的计算

通过这种方法，我们将时间复杂度$O(n^2)$压缩到了$O(20n)$，成功AC

总结

这道题的思路在于，题目给出了$A_i$元素的范围$2^{20}$，提示了我们可以将他转换成二进制数，也就是拆位；

又因为每一位只可能是1或0，我们可以借助长度为2的数组对记录元素出现的次数，避免了双重循环