概念

简单讲就是由一个集合构造出来的另一个集合，这个集合大小最小且能异或出原来集合中的任何一个数，并且不能表示出除了原集合的其他数。从别人那抄的。

线性基的性质

1. 线性基能相互异或得到原集合的所有相互异或得到的值。
2. 线性基是满足性质1的最小的集合。
3. 线性基没有异或和为0的子集。

code

ll num[70]{}, zero = 0;
const int B = 51;
bool insert(ll x) {
    for (int i = B; i >= 0; i -- ) {
        if (x & (1ll << i)) {
            if (num[i]) {
                x ^= num[i];
            } else {
                num[i] = x;
                return true;
            }
        }
    }
    zero ++;
    return false;
}

ll querymax(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = max(x, x ^ num[i]);
    }
    return x;
}

ll querymin(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = min(x, x ^ num[i]);
    }
    return x;
}

P3812 【模板】线性基

ll num[70]{}, zero = 0;
const int B = 51;
bool insert(ll x) {
    for (int i = B; i >= 0; i -- ) {
        if (x & (1ll << i)) {
            if (num[i]) {
                x ^= num[i];
            } else {
                num[i] = x;
                return true;
            }
        }
    }
    zero ++;
    return false;
}

ll querymax(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = max(x, x ^ num[i]);
    }
    return x;
}

ll querymin(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = min(x, x ^ num[i]);
    }
    return x;
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
        insert(a[i]);
    }
    cout << querymax(0) << '\n';
}

P3857 [TJOI2008] 彩灯

ll num[70]{}, zero = 0;
const int B = 50;
bool insert(ll x) {
    for (int i = B; i >= 0; i -- ) {
        if (x & (1ll << i)) {
            if (num[i]) {
                x ^= num[i];
            } else {
                num[i] = x;
                return true;
            }
        }
    }
    zero ++;
    return false;
}

ll querymax(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = max(x, x ^ num[i]);
    }
    return x;
}

ll querymin(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = min(x, x ^ num[i]);
    }
    return x;
}

void solve() {
    int n, m;
    cin >> n >> m;
    ll ans = 0;
    for (int i = 1; i <= m; i ++ ) {
        string s;
        cin >> s;
        ll val = 0;
        for (int j = 0; j < s.length(); j ++ ) {
            if (s[j] == 'O') val += (1ll << j);
        }
        if(insert(val)) ans ++;
    }
    ans = (1ll << ans) % mod;
    cout << ans << '\n';
}

P4151 [WC2011] 最大XOR和路径

ll num[70]{}, zero = 0;
const int B = 63;
bool insert(ll x) {
    for (int i = B; i >= 0; i -- ) {
        if (x & (1ll << i)) {
            if (num[i]) {
                x ^= num[i];
            } else {
                num[i] = x;
                return true;
            }
        }
    }
    zero ++;
    return false;
}

ll querymax(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = max(x, x ^ num[i]);
    }
    return x;
}

ll querymin(ll x) {
    for (int i = B - 1; i >= 0; i -- ) {
        x = min(x, x ^ num[i]);
    }
    return x;
}

int n, m, vis[N];
vector<pair<int, ll>> g[N];
ll dis[N];

void dfs(int u) {
    vis[u] = 1;
    for (auto [v, w] : g[u]) {
        if (! vis[v]) {
            dis[v] = dis[u] ^ w;
            dfs(v);
        } else {
            insert(dis[u] ^ w ^ dis[v]);
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    dfs(1);
    cout << querymax(dis[n]) << '\n';
}

2024CCPC J.找最小

int num[70]{}, zero = 0;
const int B = 31;
bool insert(int x) {
    for (int i = B; i >= 0; i -- ) {
        if (x & (1 << i)) {
            if (num[i]) {
                x ^= num[i];
            } else {
                num[i] = x;
                return true;
            }
        }
    }
    zero ++;
    return false;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    int fa = 0, fb = 0;
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
        fa ^= a[i];
    }
    for (int i = 0; i < n; i ++ ) {
        cin >> b[i];
        fb ^= b[i];
    }
    for (int i = 0; i < n; i ++ ) {
        int c = a[i] ^ b[i];
        insert(c);
    }
    for (int i = B; i >= 0; i -- ) {
        int pre = max(fa, fb);
        int now = max(fa ^ num[i], fb ^ num[i]);
        if (now < pre) {
            fa = fa ^ num[i];
            fb = fb ^ num[i];
        }
    }
    cout << max(fa, fb) << '\n';
    for (int i = 0; i < 70; i ++ ) {
        num[i] = 0;
    }
}