2.7 Xorto题解

2.7

Xorto

链接：https://ac.nowcoder.com/acm/problem/14247

题意：选两个区间(不相交且非空，异或和为0的方案数）

开始时我将异或和理解为了两个区间分别异或的和，其实异或和就是所以数异或起来。因为异或的逆运算为本身，所以可以用前缀和思想预处理\(sum[i]\),表示前i为的异或和。可以\(O(n)\)预处理

\(sum[i]=sum[i - 1]\) \(^\) \(a[i]\)

求\(l\)到 \(r\)的异或和就为\(sum[r]\) \(^\) \(sum[l - 1]\)

异或和为0的两个区间可以转换为异或和相等的区间
考虑每每一位以\(i + 1\)开头的区间，结尾是\(j\)，它的贡献就为\(1\)~\(i\)中异或和等于\(i + 1\)~\(j\)异或和的数量。所以只需用\(cnt[q]\)数组处理当前异或和为q的区间个数。

Code

#include <bits/stdc++.h>
using namespace std;
#define R 
typedef long long ll;
const int MAXN = 1e7 + 5;
int a[MAXN],sum[MAXN];
int cnt[MAXN];
int main()
{
	int n;
	scanf("%d", &n);
	for(R int i = 1;i <= n; i++)
		scanf("%d", &a[i]);
	for(R int i = 1;i <= n; i++)
		sum[i] = sum[i - 1] ^ a[i];
	ll ans = 0;
	for(R int i = 1;i <= n; i++)
	{
		for(R int j = 1;j <= i; j++)
			cnt[(sum[i] ^ sum[j - 1])]++;//加入以i结尾的区间
		for(R int j = i + 1;j <= n; j++)
			ans += cnt[(sum[j] ^ sum[i])];//查询以i + 1开头，j结尾的区间
	} 
	printf("%lld", ans);
	return 0;
}