ABC141F

shinkuu · 2023-12-22 09:49:51 · 题解

偶然找到的线性基好题。

考虑 s=\bigoplus x_i，则此时 b=s\oplus a，问题变为 \max(a+(s\oplus a))。

然后观察 s，有一个很典的想法是，s 为 0 的位上，a 如果是 0 则会产生 0 的贡献，否则产生 2，s 为 1 的位则稳定产生 1 的贡献，结合异或本质理解。

所以现在要求 x_i 的一个子集的异或和中 s 所有 0 的位组成的值的 \max。这显然是一个线性基，具体实现是将所有 x 按位与一个取反后的 s，再插入线性基。

code：

int n,m;ll c[N];
struct XXJ{
    ll a[63];
    il void insert(ll x){
        drep(i,59,0){
            if(!(x>>i&1ll))continue;
            if(a[i])x^=a[i];
            else{a[i]=x;return;}
        }
    }
    il ll query(ll x){
        drep(i,59,0)if((x^a[i])>x)x=x^a[i];
        return x;
    }
}T;
void Yorushika(){
    scanf("%d",&n);
    ll sum=0;
    rep(i,1,n)scanf("%lld",&c[i]),sum^=c[i];
    rep(i,1,n)T.insert(c[i]&(~sum));
    printf("%lld\n",2*T.query(sum)-sum);
}
signed main(){
    int t=1;
    //  scanf("%d",&t);
    while(t--)
        Yorushika();
}