思路分析

首先考虑一个朴素做法：

• 枚举所有区间 $[l,r]$
• 计算区间异或和

时间复杂度是 $O(n^2)$，当 $n=10^5$ 时显然会超时（约 $10^{10}$ 次操作）。

前缀异或优化

我们定义前缀异或和数组：

那么区间 $[l,r]$ 的异或和为：

转化问题

要求：

等价于：

核心思想

在遍历到 $r$ 时：

• 只需要统计之前有多少个满足 $b[l-1] = b[r] \oplus x$
• 用一个哈希表记录前缀异或和出现次数

特殊情况处理

当：

即：

说明区间 $[1,r]$ 本身就是一个合法区间。

为了统一处理这种情况，需要：

cnt[0] = 1;

表示“空前缀”出现过一次。

算法流程

1. 初始化：

   • cnt[0] = 1
   • ans = 0

2. 遍历数组：

   • 计算前缀异或和 b[i]
   • 查询 cnt[b[i] ^ x]
   • 累加到答案
   • 更新 cnt[b[i]]

代码实现（C++）

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

typedef long long ll;
const int N = 1e5 + 10;

int a[N], b[N];

int main() {
    int n, x;
    cin >> n >> x;

    unordered_map<int, int> cnt;
    cnt[0] = 1;

    ll ans = 0;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = b[i - 1] ^ a[i];

        if(cnt.count(b[i] ^ x)) {
            ans += cnt[b[i] ^ x];
        }

        cnt[b[i]]++;
    }

    cout << ans;
    return 0;
}

首先先写一个异或前缀和数组的预处理，这个问题求区间实际上可以用i和j枚举所有开始和结尾，然后利用[l,r]区间的异或前缀和为s[r]^s[l-1]来暴力，但是复杂度是n方。换一种思路，这里利用一下异或的性质，我们要求s[r]^s[l-1]=x的情况，这实际上等价于求s[r]^x=s[l-1]，这是异或运算的性质，那么我们可以枚举所有可能的s[l-1]，储存其值和出现的次数l-1的取值范围实际上就是0到r-1，最后统计有多少匹配的并加和即可。

import sys
input = lambda:sys.stdin.readline().strip()

n, x = map(int, input().split())
a = [0] + list(map(int, input().split()))
s = [0] * (n + 1)

for i in range(1, n + 1):
    s[i] = s[i-1] ^ a[i]

from collections import defaultdict
count = defaultdict(int)
ans = 0

for r in range(1, n + 1):
    count[s[r-1]] += 1
    tar = s[r] ^ x
    if tar in count:
        ans += count[tar]
print(ans)