题解 | 子段异或

子段异或

该问题的核心在于计算数列中异或值为0的不同子段数量。利用异或运算的性质，可以通过前缀异或和将问题转化为统计前缀异或数组中相同值的对数。具体来说，定义前缀异或数组 pref，其中 pref[i] 表示从数列开头到第 i 个元素的异或和（pref[0] = 0）。子段 [l, r] 的异或值等于 pref[r] ⊕ pref[l-1]，因此异或值为0当且仅当 pref[r] = pref[l-1]。这意味着问题等价于找到所有满足 pref[i] = pref[j] 且 i < j 的索引对 (i, j)，其中 i 和 j 对应前缀异或数组的索引（从0到n）。每个这样的对对应一个唯一子段 [i+1, j]。

算法步骤

1. 初始化：

   • 创建一个哈希表 freq 用于记录每个前缀异或值出现的频率，并初始化 freq[0] = 1（对应空前缀 pref[0] = 0）。
   • 初始化当前前缀异或值 curr_xor = 0。
   • 初始化答案计数器 count = 0。

2. 计算前缀异或和并统计频率：

   • 遍历数列中的每个元素（索引从1到n）：
     • 更新 curr_xor = curr_xor ⊕ a[i]。
     • 在哈希表 freq 中增加 curr_xor 的频次（如果存在则加1，否则设为1）。

3. 计算异或值为0的子段数量：

   • 遍历哈希表 freq 中的每个值 v：
     • 令 k = freq[v]，即值 v 出现的次数。
     • 计算组合数 C(k, 2) = k * (k - 1) / 2，并将其累加到 count 中。这表示从 k 个相同值中选择两个不同索引的所有方式数，每个方式对应一个异或值为0的子段。

4. 输出结果：返回 count 作为答案。

计算复杂度

• 时间复杂度：O(n)。计算前缀异或和和更新哈希表各需要 O(n) 时间，遍历哈希表计算组合数在最坏情况下也需要 O(n) 时间（当所有前缀异或值都不同时），因此总体是线性的。
• 空间复杂度：O(n)。哈希表在最坏情况下需要存储 O(n) 个键值对（例如当所有前缀异或值都不同时）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> prefix(n + 1);
    prefix[0] = 0;
    ll curXor = 0;
    ll cnt = 0;
    unordered_map<ll, ll> dict;
    dict[0] = 1; // prefix[0] = 0

    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        curXor ^= x;
        dict[curXor]++;
    }

    for (const auto &e : dict) {
        ll freq = e.second;
        cnt += freq * (freq - 1) / 2;
    }
    cout << cnt << endl;
}