普通消元求解线性基并求解最大异或和

#include <iostream>
#include <vector>

using namespace std;

// 定义线性基类
class LinearBasis {
public:
    long long basis[64]; // 存储线性基

    LinearBasis() {
        fill(basis, basis + 64, 0);
    }

    // 向线性基中插入一个数
    bool insert(long long x) {
        for(int i = 63; i >= 0; --i){
            if(!(x >> i)) continue;
            if(!basis[i]){
                basis[i] = x;
                return true;
            }
            x ^= basis[i];
        }
        return false;
    }

    // 获取最大异或和
    long long getMaxXorSum(){
        long long res = 0;
        for(int i = 63; i >= 0; --i){
            if((res ^ basis[i]) > res){
                res ^= basis[i];
            }
        }
        return res;
    }
};

int main(){
    vector<long long> nums = {1, 2, 3, 4}; // 输入数组
    LinearBasis lb;

    for(auto num : nums){
        lb.insert(num); // 将每个数插入线性基
    }

    cout << "Maximum XOR Sum: " << lb.getMaxXorSum() << endl; // 输出最大异或和

    return 0;
}