模板【洛谷P3812】【模板】线性基

P3812 【模板】线性基

给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

code:

#include <iostream>

#include <cstdio>

using namespace std;

#define int long long

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

const int wx=77;

int p[wx];

int n,ans;

void add(int x){

	for(int i=60;i>=0;i--){

		if(x&(1ll<<i)){

			if(!p[i]){

				p[i]=x;

				return ;

			}

			else x^=p[i];

		}

	}

}

signed main(){

	n=read();

	for(int i=1;i<=n;i++){

		int x; x=read();

		add(x);

	}

	for(int i=60;i>=0;i--)

		if((ans^p[i])>ans)ans^=p[i];

	printf("%lld\n",ans);

}

巴特西

模板【洛谷P3812】【模板】线性基

最新文章

热门文章

巴特西

模板【洛谷P3812】 【模板】线性基

最新文章

热门文章

模板【洛谷P3812】【模板】线性基