高斯消元法wa4~10求助
查看原帖
高斯消元法wa4~10求助
267184
OB_server楼主2024/9/28 18:30

如题,排序后用cpy存储原数组复制,对原数组作高斯消元求线性基,对于选中的线性基的和存入xum...但是只对了前三个点

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long

/*
高斯消元法求异或空间线性基:
A)从高到低枚举每一列c:
    (1)找到一个二进制第c位是1的数
    (2)将这个数换到第c个
    (3)将所有第c位是1的数与该数异或

复杂度O(n^2),但数字需要在ull范围内
*/
ull deg(ull num, int i){return num & (1ull << i);}

int gauss_xor(vector<ull> &x){
    vector<ull>cpy(x);
    ull xum = 0;
    int n=x.size()-1;
    int c,r;
    for(c=63,r=1; ~c && r<=n; c--){
        //(1)(2)
        for(int i=r;i<=n;i++)
            if(deg(x[i],c)){
                swap(cpy[r],cpy[i]);
                swap(x[r],x[i]);
                cout<<cpy[r]<<endl;
                xum+=cpy[r];
                break;
            };
        if(!deg(x[r],c))continue;
        //(3)
        for(int i=1;i<=n;i++)
            if(i!=r && deg(x[i],c))
                x[i]^=x[r];
        
        r++;
    }
    //x.resize(--r);
    return  xum;
}



//https://www.luogu.com.cn/problem/P3812
signed main(){
    vector<ull> a;
    int n;cin>>n;
    a.resize(n+1);
    ull xum=0,sum =0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    sort(a.begin()+1,a.begin()+n+1,[](int a,int b){
        return a>b;
    });
    
    xum=gauss_xor(a);

    cout<<sum-xum<<endl;
}
2024/9/28 18:30
加载中...