NC14247 Xorto

题意

给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。

分析

对于一个区间 ，我们统计 前面的区间中，和 前缀异或和相等的有多少即可。
我们用一个桶记录异或和出现多少次。
这样，枚举 ，对于一个 ，枚举小于等于 的 ，将 的异或和加入桶中。然后枚举大于 的 ，统计 的异或和出现多少次。加起来就是答案了。
要得到 的异或和，只需要将 的异或和异或上 的异或和即可，所以要预处理一下前缀异或和。

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 1005
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int s[N], v[N * N];
LL ans;
int main(){
    int i, j, n, m;
    n = read();
    for(i = 1; i <= n; i++) s[i] = s[i - 1] ^ read();
    for(i = 1; i <= n; i++){
        for(j = 1; j <= i; j++) v[s[i] ^ s[j - 1]]++;
        for(j = i + 1; j <= n; j++) ans += v[s[j] ^ s[i]];
    }
    printf("%lld", ans);
    return 0;
}