AtCoder Beginner Contest 141 F. Xor Sum 3（异或性质+异或线性基求最大异或值）-CSDN博客

本文链接：https://blog.csdn.net/Code92007/article/details/137661483

文章讲述了如何通过计算n个数的异或和，针对每位进行奇偶分析，将问题转化为在特定位上选择子集使异或和最大，然后结合线性背包方法求解，最终得出最大和的2倍加原异或和的结果。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

n(2<=n<=1e5)个数，第i个数ai(0<=ai<=2^60)

将n个数分成两堆，对每一堆求异或和，再将得到的两个数求和，

现在希望这个和最大，输出这个最大的值

思路来源

ABC141F - 洛谷专栏

题解

感觉思路来源说的很清楚了，

计n个数的异或和为s，考虑s的每一位，

如果第i位为1，那么说明这一位出现奇数次，不管怎么分都是一边1一边0，

如果第i位为0，那么出现偶数次，只有左右都分奇数次的时候，才有2的贡献，否则产生0的贡献

那只考虑这些第i位为0的位，问题转化成，

只考虑n个数的这些位，选出一个非空子集来，使得n个数在这些位上的异或和最大，记为mx

于是套线性基板子即可，

为0的这些位有两倍的贡献，为1的位不管怎么分都能取到，所以最终答案是2*mx+s，

代码

// Problem: F - Xor Sum 3
// Contest: AtCoder - AtCoder Beginner Contest 141
// URL: https://atcoder.jp/contests/abc141/tasks/abc141_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,M=62;
int n;
ll s,a[N],k[M];
void ins(ll x){
    per(i,60,0){
        if(x&(1ll<<i)){
            if(k[i])x=x^k[i];
            else{
                k[i]=x;
                return;
            }
        }
    }
}
ll ask(ll x){
	per(i,60,0){
		if((x^k[i])>x)x^=k[i];
	}
	return x;
}
int main(){
	sci(n);
	rep(i,1,n){
		scanf("%lld",&a[i]);
		s^=a[i];
	}
	rep(i,1,n){
		ins(a[i]&(~s));
	}
	printf("%lld\n",2ll*ask(0)+s);
    return 0;
}