线性基

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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
template<typename T>struct linear_base{
    static const int maxlog=60;
    T a[61];
    void ins(T x){
        for(T i=maxlog;i>=0;i--)
            if(x&((T)(1)<<i))
                if(!a[i]){a[i]=x;return;}
                else x^=a[i];
    }
    bool check(T x){
        for(T i=maxlog;i>=0;i--)
            if(x&((T)(1)<<i))
                if(!a[i])return 0;
                else x^=a[i];
        return 1;
    }
    T qmax(){
        T res=0;
        for(T i=maxlog;i>=0;i--)if((res^a[i])>res)res^=a[i];
        return res;
    }
    T qmin(){
        for(T i=0;i<=maxlog;i++)if(a[i])return a[i];
    }
    T query(int k){
        T tmp[maxlog+1],res=0,cnt=0;
        for(T i=0;i<=maxlog;i++){
            for(int j=i-1;j>=0;j--)if(a[i]&((T)(1)<<j))a[i]^=a[j];
            if(a[i])tmp[cnt++]=a[i];
        }
        for(T i=0;i<cnt;i++)if(k&((T)(1)<<i))res^=tmp[i];
        return res;
    }
};
linear_base<ll>s;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){ll x;scanf("%lld",&x);s.ins(x);}
    printf("%lld\n",s.qmax());
    return 0;
}

results matching ""

    No results matching ""