Linear basis count (k large XOR sum)

Linear basis counting （k Great difference or and ）

link ：#114. k Great difference or and - subject - LibreOJ (loj.ac)

The question ： Given a reproducible set S, Ask many times for the first k Small true subsets XOR and .

Answer key ： Reconstruct the linear basis , send $p[i]$ Of the j Bit in $p[j]$ In case of existence, it is not 1, So XOR $p[j]$ It must make the value larger , Abstracting into binary is to take $p[j]$ amount to j Position fetching 1, Then you can put k Check the XOR result by bit .

tips： When the number of linear bases $cnt$ Less than n when , Explain the non full rank , All results can be XOR 0, So it seems that the 1 As small as 0 Instead of $p[0]$, So for k Minus one . The total XOR result is no more than $2^{cnt}-1$ Of .

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

using namespace std;
typedef long long ll;
const int maxn=55;

ll p[maxn],f[maxn],cnt,n,m,ans,u,v,w;

inline 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;
}

inline void rebuild()
{
    
	for(int i=0;i<=50;i++)
	{
    
		for(int j=i-1;j>=0;j--)
		{
    
			if(p[i]>>j&1)p[i]^=p[j];
		}
		if(p[i])f[cnt++]=p[i];
	}
	return;
}

inline ll query(ll k)
{
    
	if(cnt!=n)k--;
	if(k>=(1ll<<cnt))return -1;
	ll ans=0;
	for(int i=0;i<cnt;i++)ans^=f[i]*(k>>i&1);
	return ans;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
    
		cin>>u,insert(u);
	}
	rebuild(),cin>>m;
	for(int i=1;i<=m;i++)
	{
    
		ll k; cin>>k,cout<<query(k)<<"\n";
	} 
	return 0;
}