题面描述

给定一个序列 $a$：$a[1], a[2], a[3], \dots, a[n]$，以及一个数 $x$，请计算满足以下两个条件的非空区间 $[L, R]$ 的个数：

1. 区间 $[L, R]$ 中所有元素的异或值等于 $x$，即 $a[L] \oplus a[L+1] \oplus \dots \oplus a[R] = x$。
2. 区间的长度为偶数，即 $(R - L + 1) \bmod 2 = 0$。

思路

对于一段区间$[l,r]$的异或和等于[1,r]的异或和异或[1,l-1]的异或和，那么对于奇数下标的前缀异或和，如果与之前的奇数下标的前缀异或和异或为$x$说明答案可以++，偶数同理，我们用两个哈希表分别记录偶数与奇数的前缀异或和为w ^ x的区间那么如果当前下标奇偶性相同且前缀异或和为$w$那么这段$[l,r]$的区间异或和就是$x$

具体实现

1. 前缀异或数组：首先，计算前缀异或数组 prefix，其中 prefix[i] = a[1] ⊕ a[2] ⊕ ... ⊕ a[i]。这样，区间 $[L, R]$ 的异或值可以通过 prefix[R] ⊕ prefix[L-1] 来计算。

2. 满足异或条件：根据前缀异或的性质，我们需要满足 prefix[R] ⊕ prefix[L-1] = x，即 prefix[L-1] = prefix[R] ⊕ x。这意味着，对于每个位置 $R$，我们需要找到之前位置 $L-1$，使得 prefix[L-1] 等于 prefix[R] ⊕ x。

3. 考虑区间长度的奇偶性：题目要求区间长度为偶数，即 (R - L + 1) % 2 = 0。这等价于 (R - (L-1)) % 2 = 0，即位置 $R$ 和位置 $L-1$ 的奇偶性相同。因此，我们需要分别维护两个哈希表，分别记录前缀异或值在偶数位置和奇数位置出现的次数。

4. 统计答案：遍历序列，维护当前的前缀异或值和当前位置的奇偶性。对于每个位置 $R$，计算 prefix[R] ⊕ x，并在对应奇偶性的哈希表中查找是否存在相应的 prefix[L-1]，累加符合条件的次数

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &x : a) cin >> x;
    int x;
    cin >> x;
    
    // 两个哈希表，分别记录偶数位置和奇数位置的前缀异或出现次数
    unordered_map<int, int> cnt_even, cnt_odd;
    // 初始时，前缀异或为0，位置为0（偶数位置）
    cnt_even[0] = 1;
    
    ll prefix = 0;
    ll ans = 0;
    for(int i=1;i<=n;i++){
        prefix ^= a[i-1];
        // 计算需要的前缀值
        int desired = prefix ^ x;
        // 判断当前位置的奇偶性
        if(i % 2 == 0){
            // 当前是偶数位置，查找在偶数位置出现的desired次数
            if(cnt_even.find(desired) != cnt_even.end()){
                ans += cnt_even[desired];
            }
            // 更新偶数位置的前缀异或次数
            cnt_even[prefix]++;
        }
        else{
            // 当前是奇数位置，查找在奇数位置出现的desired次数
            if(cnt_odd.find(desired) != cnt_odd.end()){
                ans += cnt_odd[desired];
            }
            // 更新奇数位置的前缀异或次数
            cnt_odd[prefix]++;
        }
    }
    cout << ans;
}

python

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取第一行，n
        int n = Integer.parseInt(br.readLine());
        // 读取第二行，序列a
        String[] aStr = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(aStr[i]);
        // 读取第三行，x
        int x = Integer.parseInt(br.readLine());
        
        // 使用两个HashMap分别记录偶数位置和奇数位置的前缀异或出现次数
        HashMap<Integer, Integer> cnt_even = new HashMap<>();
        HashMap<Integer, Integer> cnt_odd = new HashMap<>();
        // 初始时，前缀异或为0，位置为0（偶数位置）
        cnt_even.put(0, 1);
        
        long prefix = 0; // 保持为long类型以处理大范围
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            prefix ^= a[i - 1];
            int desired = (int) (prefix ^ x); // 确保desired为int类型
            
            if (i % 2 == 0) {
                // 当前是偶数位置，查找在偶数位置出现的desired次数
                ans += cnt_even.getOrDefault(desired, 0);
                // 更新偶数位置的前缀异或次数
                cnt_even.put((int) prefix, cnt_even.getOrDefault((int) prefix, 0) + 1);
            } else {
                // 当前是奇数位置，查找在奇数位置出现的desired次数
                ans += cnt_odd.getOrDefault(desired, 0);
                // 更新奇数位置的前缀异或次数
                cnt_odd.put((int) prefix, cnt_odd.getOrDefault((int) prefix, 0) + 1);
            }
        }
        System.out.println(ans);
    }
}

题目内容

给你一个序列$a$:$a[1],a[2],a[3],...,a[n]$。给一个数$x$，求满足下列条件的非空区间$[L,R]$的个数：

$a[L]^a[L+1]...^a[R] = x$，即区间异或值为$x$

$(R - L + 1)$%$2 = 0$，即区间长度为偶数。

输入说明

输入描述

第一行输入$n$表示序列长度

第二行输入一个序列$a$，第三行$x$

$1≤len(a)≤10^5$

$0≤x≤10^9$

输出描述

输出答案

样例1

输入

5
1 2 3 2 1
2		

输出

2