AcWing 4507. 子数组异或和

• 异或性质和加法很类似，又被称为 不进位加法，因此如果要求某一个区间的异或和，可以先预处理一个前缀和
• 如果区间最右端点为i，且区间长度一共为2m，条件2转换为：
  $s[i]$ ^ $s[i-m+1-1]=s[i-m]$ ^ $s[i-2\ast m+1-1]$
  $S_i$ ^ $S_{i-m}=S_{i-m}$ ^ $S_{i-2m}$
  $S_{i-m}$ ^ $S_{i-m}$ = $S_i$ ^ $S_{i-2m}$
  $S_i$ ^ $S_{i-2m}=0$
  $S_i=S_{i-2m}$
• 条件1区间长度为偶数，说明右端点和左端点奇偶性一致；我们可以用两个哈希表，更进一步地，用一个二维哈希表，用 & 1表示奇偶性；因此，两个条件转化为了遍历右端点，答案加上与右端点差偶数位上的前缀异或和相等的数量
• 注意要初始化！！！s[0][0] = 1，表示下标为0，sum为0的情况
• 注意我们枚举右端点

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
#define one first
#define two second
#define pb push_back
using namespace std;
template<class T> void chkmax(T &a, T b) {a = max(a, b);}
template<class T> void chkmin(T &a, T b) {a = min(a, b);}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    unordered_map<ll, ll> ma[2];
    ll ans = 0, sum = 0;
    ma[0][0] = 1;
    for (int i = 1, x; i <= n && cin >> x; ++ i) {
        sum ^= x;
        ans += ma[i & 1][sum];
        ma[i & 1][sum] ++ ;
    }
    cout << ans;
}

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
35
36
37
38
39
40
41
42
43