本文主要是介绍Codeforces Contest 1101 problem G (Zero XOR Subset)-less —— 线性基，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
inputCopy
4
5 5 7 2
outputCopy
2
inputCopy
3
1 2 3
outputCopy
-1
inputCopy
3
3 1 10
outputCopy
3
Note
In the first example 2 is the maximum number. If you divide the array into {[5],[5,7,2]}, the XOR value of the subset of only the second segment is 5⊕7⊕2=0. {[5,5],[7,2]} has the value of the subset of only the first segment being 5⊕5=0. However, {[5,5,7],[2]} will lead to subsets {[5,5,7]} of XOR 7, {[2]} of XOR 2 and {[5,5,7],[2]} of XOR 5⊕5⊕7⊕2=5.
Let’s take a look at some division on 3 segments — {[5],[5,7],[2]}. It will produce subsets:
{[5]}, XOR 5;
{[5,7]}, XOR 2;
{[5],[5,7]}, XOR 7;
{[2]}, XOR 2;
{[5],[2]}, XOR 7;
{[5,7],[2]}, XOR 0;
{[5],[5,7],[2]}, XOR 5;
As you can see, subset {[5,7],[2]} has its XOR equal to 0, which is unacceptable. You can check that for other divisions of size 3 or 4, non-empty subset with 0 XOR always exists.
The second example has no suitable divisions.
The third example array can be divided into {[3],[1],[10]}. No subset of these segments has its XOR equal to 0.
题意：
给你n个数，让你分成尽可能多的集合，使得任意集合的异或不为0
题解：
第一次遇到线性基的题目，这道题就是求线性无关的秩
别人的模板
#include<bits/stdc++.h>
using namespace std;
int a[35];
int main()
{int n;scanf("%d",&n);int ans=0,ret=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);ret^=x;for(int j=31;j>=0;j--){if((x&(1<<j))){if(a[j])x^=a[j];else{a[j]=x,ans++;break;}}}}printf("%d\n",ret==0?-1:ans);return 0;
}这篇关于Codeforces Contest 1101 problem G (Zero XOR Subset)-less —— 线性基的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
