【LOJ#6060】Set（线性基）

【LOJ#6060】Set（线性基）

题面

LOJ

题解

好题啊QwQ。

首先\(x1\oplus x2=s\)是定值。而\(s\)中假设某一位上是\(1\)，则\(x1,x2\)上必定有一个是\(1\)，另一个是\(0\)，所以对答案没有影响。反过来，如果\(s\)上某一位为\(0\)，则要么都是\(0\)，要么都是\(1\)。

所以我们在考虑构造线性基的时候，优先考虑\(0\)的位，再考虑\(1\)的位。

那么现在只需要令\(x2\)在原本在\(s\)是\(0\)的位置上取到尽可能多的\(1\)的情况下最大，这样子异或一下就是\(x1\)了。（好乱啊）

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

#define MAX 100100

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n;ll a[MAX],s,p[70],s1,s2;

int b[70],tot;

void insert(ll x)

{

	for(int i=1;i<=tot;++i)

		if(x&(1ll<<b[i]))

		{

			if(!p[i]){p[i]=x;break;}

			else x^=p[i];

		}

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=read(),s^=a[i];

	for(int i=62;~i;--i)if(!(s&(1ll<<i)))b[++tot]=i;

	for(int i=62;~i;--i)if(s&(1ll<<i))b[++tot]=i;

	for(int i=1;i<=n;++i)insert(a[i]);

	for(int i=1;i<=tot;++i)if(!(s2&(1ll<<b[i])))s2^=p[i];

	printf("%lld\n",s^s2);

	return 0;

}