思路分析

首先考虑一个朴素做法：

• 枚举所有区间 $[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;
}