You are given an array a1,a2,…,an
of integer numbers.
Your task is to divide the array into the maximum number of segments in such a way that:
- each element is contained in exactly one segment;
- each segment contains at least one element;
- there doesn’t exist a non-empty subset of segments such that bitwise XOR of the numbers from them is equal to 0
- .
Print the maximum number of segments the array can be divided into. Print -1 if no suitable division exists.
Input
The first line contains a single integer n
(1≤n≤2⋅105
) — the size of the array.
The second line contains n
integers a1,a2,…,an (0≤ai≤109
).
Output
Print the maximum number of segments the array can be divided into while following the given constraints. Print -1 if no suitable division exists.
Examples
Input
4
5 5 7 2
Output
2
Input
3
1 2 3
Output
-1
Input
3
3 1 10
Output
3
题意：给你一些树，让你给树分组，然后把每一个分组看成元素，满足没有元素集合的异或和位0。
思路：首先知道一点，我们得到线性基的时候，当1的个数num（基底个数）不等于元素个数时，表示可以拼凑出0 ；那么，如果全部数的异或为0，那么无解；否则，我们现在得到了线性基，最多划分为几个集合呢，答案就是num。 因为这num个位置的最高位1的位置不同，他们是线性无关的。
（给出N个数,要从中选出一个最大的子集,使得子集中的任意个元素异或值不为0，答案也是基底
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int p[],ans;
int main()
{
int N,sum=,num=,x;
scanf("%d",&N);
rep(i,,N) {
scanf("%d",&x); sum^=x;
rep2(j,,){
if(x&(1LL<<j)){
if(p[j]) x^=p[j];
else { p[j]=x;break;}
}
}
}
if(sum==) return puts("-1"),;
rep(i,,) if(p[i]){
p[num++]=p[i];
rep(j,i+,) if((p[j]>>i)&) p[j]^=p[i];
}
printf("%d\n",num);
return ;
}
