摘要
Title: 4507. 子数组异或和
Tag: 异或和、哈希表
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

4507. 子数组异或和

• 题意

  给定一个长度为 n 的整数数组 a1,a2,…,an。
  请你统计一共有多少个数组 a 的非空连续子数组能够同时满足以下所有条件：
  该连续子数组的长度为偶数。
  该连续子数组的前一半元素的异或和等于其后一半元素的异或和。

• 思路

  该连续子数组的长度为偶数：说明了区间端点，j-i是偶数
  该连续子数组的前一半元素的异或和等于其后一半元素的异或和：

  • 易证：为该区间的异或和等于0
  • 假设前半段的异或和为x，后半段为y，x = y, x ^ y = y ^ y, 则x ^ y = 0
  • 所以其实不一定是前一半，前1/3，结果也是这个结论

  实现的话，先初始化异或前缀和数组，开两个哈希表即可，记录奇数位和偶数位每个数的情况
  另外要注意初始化，当下标位偶数时，其异或前缀和位0时，也算一种情况（因b[0] = 0）

  异或前缀和的性质
  s[i]=s[i−1]⊕a[i]
  a[l]⊕a[l+1]⊕…⊕a[r]=s[r]⊕s[l−1]

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-08-16 08:52:35
  * @FilePath: \Acwing\4507\4507.cpp
  * @LastEditTime: 2022-08-16 09:12:47
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define N n + 100
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  signed main()
  {
      IOS;
      int n;
      cin >> n;
      vector<int> a(N), b(N);
      unordered_map<int, int> odd, even;
  
      for (int i = 1; i <= n; ++i)
      {
          cin >> a[i];
          b[i] = b[i - 1] ^ a[i];
      }
      int ans = 0;
      odd[0]++;
      for (int i = 1; i <= n; ++i)
      {
          if (i % 2 == 0)
          {
              ans += odd[b[i]];
              odd[b[i]]++;
          }
          else
          {
              ans += even[b[i]];
              even[b[i]]++;
          }
      }
      cout << ans;
      return 0;
  }