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

目录

• 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.样例输出

    39
    

    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∑20​2i×bi​

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

    3. AC_Code

    • C++

      #include
      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 
      		int x;
      		cin > x;
      		for (int j = 0; j 
      			a[i][j] = (x > j) & 1;
      			a[i][j] ^= a[i - 1][j];
      		}
      	}
      	LL ans = 0;
      	for (int j = 0; j 
      		map
      			int x = m[a[i][j] ^ 1];
      			ans += 1LL * (1 
          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 
                  int x = scan.nextInt();
                  for (int j = 0; j 
                      a[i][j] = (x  j) & 1;
                      a[i][j] ^= a[i - 1][j];
                  }
              }
              long ans = 0;
              for (int j = 0; j 
                  Map
                      int x = m.getOrDefault(a[i][j] ^ 1, 0);
                      ans += (1L 0: 1}
          for i in range(1, n + 1):
              x = m.get(a[i][j] ^ 1, 0)
              ans += (1