Linear basis

Linear base Basic template

link ：#113. The greatest exclusive or and - subject - LibreOJ (loj.ac)

Given a reproducible set s , Find a proper subset , Maximize the exclusive or sum of all numbers in the true subset .

• Reproducible set s Any number in a linear basis can have an exclusive or of numbers in a linear basis .
• The exclusive or sum of any proper subset in a linear basis is not 0 .

1. $p_i$ It means the first one i Position as 1 And is the highest number .（ Then the lower order of the time does not affect the higher order ）
2. Reduce the dimension of high-dimensional data during insertion .

When inserting data , To make x Exclusive or sum with a proper subset in a linear base is 0 , Indicates that... Can be synthesized x , Then judge from high to low bit by bit x , Ruodi i Position as 0 , Then this bit does not need any data XOR representation in the set ; if 1, Then check whether there is no i Whether the linear basis of bit exists , If it doesn't exist x Act as a base and exit , If it exists, it will x Low dimensional . In the end, there is no such thing as x Operate as a base , send x by 0 It means that the current linear basis can be synthesized x, No need to insert .
Answer key ： Observe the topic , Find a subset to maximize the XOR sum , You just need to make the high order as 1 that will do .

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxn=1<<6;

ll p[maxn],n,a;

void insert(ll x)
{
    
	for(int i=50;i>=0;i--)
	{
    
		if(x>>i&1)
		{
    
			if(!p[i]){
    p[i]=x; break;}
			x^=p[i];
		}
	}
	return;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
    
		cin>>a,insert(a);		
	}
	ll ans=0;
	for(int i=50;i>=1;i--)
	{
    
		ans=max(ans,ans^p[i]);
	}
	cout<<ans<<"\n";
	return 0;
}