本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16179653.html

D1T2 数列游戏

题目

有一个长度为 $n$ 的序列 $a_1, \dots , a_n$ 。

如果序列的长度大于 1，那么你就能进行操作，每次操作可以选择两个相邻的数 $a_i, ai+1$ 合并，得到一个新的数 $a_i$ ⊕ $a_{i+1}$ （“⊕”表示异或），每次操作都会使序列的长度减少 1。例如对将序列 $[8, 3, 5, 7, 1]$ 中的第 2个和第 3 个数进行合并，会得到新序列 $[8, 6, 7, 1]$ ，并可以进行下一轮操作。

你需要进行若干次操作（可能是 0 次），使得最终序列任意子区间的异或和不为 0。子区间的定义为连续的一段数 $ [a_l, a_{l+1}, \dots ,a_r]（l \leqslant r）$。

求满足条件的最终序列的最长长度。

思路

记数列 $a$ 的异或前缀和为 $s$ ，则区间 $[l, r]$ 的异或和为 $s_r$ ⊕ $s_{l-1}$ 。

我们要使任意区间异或和不为0，就是要是 $s$ 互不相同且皆大于0.

因此，我们要将不符合要求的 $s$ 消除。

假如我们想要让某个 $s_i$ 消除，我们只需要合并 $i$ 和 $i+1$ 即可。

但在程序实现的过程中，我们并不需要模拟消除，只需要统计多少个不同的即可。

无解的情况是整个数列异或和为0。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'
){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x
<<3)+(ch^48);ch=getchar();}return x*f;}
//#define N
//#define M
//#define mo
int n, m, i, j, k, T;
map<int, int>mp; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin);
//	freopen("tiaoshi.out", "w", stdout);
	n=read(); mp[0]=1; 
	for(i=1; i<=n; ++i)
	{
		j=read(); k^=j; 
		if(!mp[k]) ++m, mp[k]=1; 
	}
	printf("%lld", (k==0 ? -1 : m)); 
	return 0;
}

总结

这道题在考场上没想出来，值得反思。

对于区间异或和的问题，可以多思考前缀异或和的思想。

而区间异或和为0的情况，就是存在前缀异或和相等。

以后对于区间异或的情况可以多往这个方面想。