线性基

原理

见《进阶指南》第166页。

模板题

洛谷-P3812-【模板】线性基

#include <iostream>
using namespace std;

typedef unsigned long long ULL;
const int N = 70;
ULL a[N], p[N];

void insert (ULL x) {
    for (int i = 61; i >= 0; -- i) {
        if ((x >> i) & 1) {
            if (p[i] == 0) {
                p[i] = x;
                return;
            }
            x = x ^ p[i];
        }
    }
}

int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    for (int i = 1; i <= n; ++ i) insert(a[i]);
    ULL res = 0;
    for (int i = 61; i >= 0; -- i) res = max(res, res ^ p[i]);
    cout << res << endl;
    return 0;
}