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

男娘i 2023-10-13 16:59 11阅读 0赞

#### 目录 ####

*  1. 异或和之和
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6. 数据范围
     *  7. 原题链接
 *  2. 解题思路
 *  3. AC\_Code

## 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.样例输入 ###

5
    1 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. 原题链接 ###

[异或和之和][Link 1]

## 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 = 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)

[Link 1]: https://www.lanqiao.cn/problems/3507/learning/