题解

考虑前缀异或和，本题即需要找到最多的点使得 $\{sump_1,sump_2⊕sump_1,⋯ ,sump_{n−1}⊕sump_n\}$ 的子集的异或非零 。

对于每个数，尝试将其插入线性基，若插入失败，则选择该点会导致子集异或和为零。最大划分数量为线性基大小。由于线性基数量唯一，从前往后遍历即可。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
using PII=std::pair<int,int>;
using i64=long long;
struct LB{
	using i64=long long;
	const int BASE=63;
	std::vector<int> d,p;
	int cnt,zero;
	LB(){
		d.resize(BASE+1);
		p.resize(BASE+1);
		cnt=zero=0;
	}
	bool insert(i64 val){
		for(int i=BASE-1;i>=0;i--){
			if(val>>i&1){
				if(!d[i]){
					d[i]=val;
					return true;
				}
				val^=d[i];
			}
		}
		zero=1;
		return false;
	}
	
};
void solve(){
	int n;std::cin>>n;
	std::vector<int> s(n+1);
	for(int i=1;i<=n;i++)std::cin>>s[i];
	for(int i=1;i<=n;i++)s[i]^=s[i-1];
	if(s[n]==0){
		std::cout<<"-1\n";
		return;
	}
	LB lb;
	int ans=0;
	for(int i=1;i<=n;i++){
		if(lb.insert(s[i]))ans++;
	}
	std::cout<<ans<<'\n';
}

signed main(){
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	std::cout<<std::fixed<<std::setprecision(10);
	int T=1;
	//std::cin>>T;
	while(T--)solve();
	return 0;
}