Xorto

题意

有多少对区间，这对区间数的亦或和为0

思路

记录一个亦或前缀和，枚举i，i将区间分为半部分和右半部分，每次从左半部分和右半部分取一个凑一对。左半部分区间亦或和存在一个数组中。

复杂度

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define db double
#define mp make_pair
#define fi first
#define se second
#define de(a) cout << #a << " = " << a << endl

ll cnt[1000010];
int pre[10010];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> pre[i];
        pre[i] ^= pre[i - 1];
    }

    ll ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            cnt[pre[i] ^ pre[j]]++;
        }
        for(int j = i + 1; j <= n; j++){
            ans += cnt[pre[j] ^ pre[i]];
        }
    }
    cout << ans << endl;

    return 0;
}