题目

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

输入描述: 
第一行一个数n表示数组长度;第二行n个整数表示数组;1<=n<=1000,0<=数组元素<100000。

输出描述:
一行一个整数表示答案。


解析

题目表意很清楚,就是两个不重合子集的异或和为0
这里显然不可能暴力搜索,所以要用到前缀和(详情见前缀和专栏)
  1. 依旧是存好数组
  2. 做一个两层循环:(第一层)用来遍历数组。(第二层)用于求以第一层遍历的位置为基点的左右两边的子集(左右子集必须包含这个基点)的异或和的数量。
  3. 散列表(map)存储某一个异或和在基点以前的数量。map[n]=m:意为异或和为n的子集有m个。
  4. 关于异或和数量:第二层有两个循环:第一个用于累加左边的散列表存储,第二个用于累加计算当前右子集的所有成功匹配的数量。
for (ll i = 2; i <= n; i++) {
    for (ll j = 1; j < i; j++)
        map[sum[j - 1] ^ sum[i - 1]]++;
    for (ll j = i; j <= n; j++)
        cnt += map[sum[i - 1] ^ sum[j]];
}


图解

解释:当i指到某个位置时,从i前面断开,循环累加计算的左右子集一定包含下划线的数据。


前缀和

ps:其实写这道题之前,我都不咋知道前缀和这个东西,tcl
前缀和:
    将具有一定关系的数组的所有前缀,按这种关系计算后,保存下来。
前缀应用举例1:
    求一个数组的第i个数到第j个数之和(默认i<j):我们平常可能就会从第i个遍历到第j个进行累加。
    前缀和方法:输入时储存第i个位置的前i项和。以得到所有前缀。所以第i个数到第j个数之和可以表示为:
本题应用:
    异或也满足前缀和的使用。所以储存下每个位置的前n项异或。
    所以第i个数到第j个数的异或和可以表示为:


AC代码

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX = 1e6 + 7;

int main() {
    js;
    vector<ll> e, sum;
    ll map[MAX];
    ll n; cin >> n;
    e.push_back(0);
    sum.push_back(0);
    for (ll i = 1; i <= n; i++) {
        ll t; cin >> t;
        e.push_back(t);
        sum.push_back(sum[i - 1] ^ t);//前缀和初始化
    }
    memset(map, 0, sizeof(map));
    ll cnt = 0;
    for (ll i = 2; i <= n; i++) {
        for (ll j = 1; j < i; j++)
            map[sum[j - 1] ^ sum[i - 1]]++;
        for (ll j = i; j <= n; j++)
            cnt += map[sum[i - 1] ^ sum[j]];
    }
    cout << cnt << endl;
    return 0;
}