WA20ptc 求优化模板
查看原帖
WA20ptc 求优化模板
1010570
A__kkksc03__A楼主2025/8/1 17:28
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int base=51;
namespace linearBasis{
    int cnt=0;
    int p[200005];
    int d[200005];
    void clear(){//清空
        cnt=0;
        for(int i=0;i<=base+5;i++){
            p[i]=0;
        }
    }
    void build(){//构造线性基
        cnt=0;
        for(int i=base;i>=0;i--){
            for(int j=i-1;j>=0;j--){
                if(p[i]&(1LL<<j)){
                    p[i]^=p[j];
                }
            }
        }
        for(int i=0;i<=base;i++){
            if(p[i]){
                d[cnt++]=p[i];
            }
        }
    }
    void ins(int x){//插入
        for(int i=base;i>=0;i--){
            if(x&(1<<i)){
                if(!p[i]){
                    p[i]=x;
                    cnt++;
                    break;
                }
                else{
                    x^=p[i];
                }
            }
        }
    }
    bool ask(int x){//是否可以异或出x
        for(int i=base;i>=0;i--){
            if(x&(1LL<<i)){
                x^=p[i];
            }
        }
        return x==0;
    }
    int getmax(int res=0){//查找最大的异或和
        for(int i=base;i>=0;i--){
            res=max(res,res^p[i]);
        }
        return res;
    }
    int getmin(int res=0){//查找最小的异或和
        for(int i=0;i<=base;i++){
            if(p[i]){
                return p[i];
            }
        }
    }
    int getk(int k){//查找第k大的异或和
        if(k>=(1<<cnt)){
            return -1;
        }
        int ans=0;
        for(int i=base;i>=0;i--){
            if((k>>i)&1){
                ans^=d[i];
            }
        }
        return ans;
    }
    int getrank(int x){//查询排名
        int ans=0,now=1;
        for(int i=0;i<=base;i++){
            if(d[i]!=0){
                if(x&(1LL<<(63-__builtin_clzll(d[i])))){
                    ans+=now;
                }
                now*=2;
            }
        }
        return ans;
    }
};
signed main(){
    using namespace linearBasis;
    int n;
    cin>>n;
    clear();
    while(n--){
        int temp;
        cin>>temp;
        ins(temp);
    }
    //build();
    cout<<getmax();
    return 0;
}
//For The Greater Good
2025/8/1 17:28
加载中...