【每日一题0414】异或前缀和

https://ac.nowcoder.com/acm/problem/14247
给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。

异或前缀和

序列[5,1,1]
pre[1]=5 pre[2]=5^1 pre[3]=5^1^1
区间[2,3]的异或则=pre[3]^pre[1]=5^1^1^5 ， 即去掉pre[1]

本题

思路在代码注释

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

int pre[10004], cnt[3000006];
int main()
{
    int n;
    scanf("%d", &n);
    memset(cnt, 0, sizeof(cnt));
    pre[0] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        pre[i] = pre[i - 1] ^ x;
        //cout << pre[i] << endl;
    }

    ll sum = 0;
    for (int i = 1; i <= n; i++) {//枚举右端点
        //printf("i=%d\n", i);
        for (int j = i; j > 0; j--) {
            //cout << (pre[i] ^ pre[j - 1]) << endl;
            cnt[pre[i] ^ pre[j - 1]]++;//左边区间[j,i]的异或和pre[i] ^ pre[j - 1]记录下来
        }
        for (int j = i; j < n; j++)
            sum += cnt[pre[i] ^ pre[j + 1]];//看看左边有多少个等于右边区间[i+1,j+1]的异或和pre[i] ^ pre[j + 1]，更左边的比如此时i=3，（1，1）在i=1时已经统计进去了
    }

    printf("%lld\n",sum);

    return 0;
}