Xorto

Xorto

题目描述

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

输入描述:

第一行一个数n表示数组长度；
第二行n个整数表示数组；
1<=n<=1000,0<=数组元素<100000。

输出描述:

一行一个整数表示答案。

示例1

输入

3
0 0 0

输出

5

说明

([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3])

可以用像前缀和一样做，也可以依次求。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1010;
int a[N], ans[1000100];
int main() {
    int n;scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
    }
    ll sum = 0;
    for(int i = 1; i <= n; i ++) {
        int tmp = 0;
        for(int j = i; j <= n; j ++) {
            tmp ^= a[j];
            if(ans[tmp]) sum += 1LL*ans[tmp];
        }
        tmp = 0;
        for(int j = i; j >= 1; j --) {
            tmp ^= a[j];
            ans[tmp] ++;
        }
    }
    printf("%lld
",sum);
    return 0;
}