当前位置：首页 > 卖家故事 > 第十四届蓝桥杯省赛 C/C++ A 组 H 题——异或和之和（AC）

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

时间：2024-04-16 12:30:54 来源：网络cs 作者：峨乐栏目：卖家故事阅读：

标签：

阅读本书更多章节>>>>

1. 异或和之和

1.题目描述

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

2.输入格式

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

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

3.输出格式

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

4.样例输入

51 2 3 4 5

5.样例输出

6. 数据范围

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

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

对于所有评测用例， 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105， 0 ≤ A i ≤ 2 20 0 \leq A_i \leq 2^{20} 0≤Ai≤220。

7. 原题链接

异或和之和

2. 解题思路

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

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

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

a i ⊕ a i + 1 ⊕ ⋯ ⊕ a j − 1 ⊕ a j = ( a 1 ⊕ a 2 ⊕ ⋯ a j ) ⊕ ( a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i − 1 ) 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}) ai⊕ai+1⊕⋯⊕aj−1⊕aj=(a1⊕a2⊕⋯aj)⊕(a1⊕a2⊕⋯⊕ai−1)

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

a i ⊕ a i + 1 ⊕ ⋯ ⊕ a j − 1 ⊕ a j = S i − 1 ⊕ S j a_i \oplus a_{i+1} \oplus \cdots \oplus a_{j-1} \oplus a_j=S_{i-1} \oplus S_j ai⊕ai+1⊕⋯⊕aj−1⊕aj=Si−1⊕Sj

如果想使得等式左边等于 1 1 1，即需要满足 S i − 1 ≠ S j S_{i-1} \ne S_j Si−1=Sj。

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

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

∑ i = 0 20 2 i × b i \sum_{i=0}^{20} 2^{i} \times b_i i=0∑202i×bi

时间复杂度： O ( 20 × n ) O(20 \times n) O(20×n)。

3. AC_Code

C++

#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 = 100010a = [[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 = 0for 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) + 1print(ans)