luogu3812 线性基模板

​​http://www.elijahqi.win/archives/1683​​​题目背景

这是一道模板题。

题目描述

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

输入输出格式

输入格式：

第一行一个数n，表示元素个数

接下来一行n个数

输出格式：

仅一行，表示答案。

输入输出样例

输入样例#1： 复制

2

1 1

输出样例#1： 复制

1

说明

1≤n≤50,0≤Si≤250 1 \leq n \leq 50, 0 \leq S_i \leq 2 ^ {50} 
 1≤n≤50,0≤S 
 i      

​

≤2

50

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[55],p[55];
int n;
inline bool cmp(long long a,long long b){
    return a>b;
}
int main(){
//  freopen("a.in","r",stdin);
    scanf("%d",&n);long long M=0;
    for (int i=1;i<=n;++i) scanf("%lld",&a[i]),M=max(M,a[i]);
    int len=log2(M);
    for (int i=1;i<=n;++i){
        for (int j=len;j>=0;--j){
            if (!(a[i]>>j)) continue;
            if (!p[j]){p[j]=a[i];break;}
            a[i]^=p[j];
        }
    }long long ans=0;
    sort(p,p+len+1,cmp);
    for (int i=0;i<=len;++i) if ((p[i]^ans)>ans) ans=p[i]^ans;
    //for (int i=1;i<=len;++i) printf("%lld ",p[i]);
    printf("%lld",ans);

    return 0;
}