线性基 - qnxy

Link

Idea

易知给出的正整数和它们任意异或后的所有结果和 $0$ 组成的集合 $G$ 关于异或运算封闭，且为有限集合，满足结合律，有单位元和逆元。所以 $G$ 构成一个群。我们求的线性基是这个群的最小线性基，即 $G$ 中的所有元素均可被基中的元素线性表出。

构造线性基的方法详见 insert 函数。

要找到 $G$ 中最大的异或和，就在线性基中由高位到低位尝试异或出最大的结果，贪心可得。

查询某数是否可被 $G$ 中元素异或得到，也是在线性基中尝试从高位到低位构建。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 1e5 + 10;

ll p[N], n, a[N], ans;

void insert(ll x) 
{
    for (int i = 63; ~i; i--) {
        if (!(x >> i)) 
            continue;
        if (!p[i]) {
            p[i] = x;
            return;
        } else 
            x ^= p[i];
    }
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        insert(a[i]);
    }
    for (int i = 63; ~i; i--) 
        ans = max(ans, ans ^ p[i]);
    printf("%lld", ans);
    return 0;
}