什么是线性基？

线性基是一个集合
从原集合中选取任意多个数异或得到的值都能通过线性基中选取一些数进行异或得到。
也就是说线性基是对原集合的压缩

如何压缩呢？

对于集合$A=${$a_{1},a_{2},\ldots,a_{n}$}, 将其中的$a_{i}(i \in[1, n])$用$a_{i}{ }^{\wedge} a_{j} （ j \in[1, n] 且 j \neq i ）$替换得到集合
$$B={a_{1}, a_{2}, \ldots, a_{i}-1, a_{i} \wedge a_{j}, a_{i}+1, \ldots, a_{n}}$$
从集合$A$中选取任意多个数异或得到的值都能通过在集合$B$中选取一些数进行异或得到

证：从原集合$A$中选取一些数异或得到
$$x=a_{k 1}{ }^{\wedge} a_{k 2}{ }^{\wedge} \ldots{ }^{\wedge} a_{k m}(k j \in[1, n]),$$
如果这些数中不包含$ai$, 那么这些数也在集合$\mathrm{B}$中, $\mathbf{x}$也能通过在$B$中取这些数异或得到, 如果包含ai, 则ai可以用$\left(a_{i}^{\wedge} a_{j}\right)^{\wedge} a_{j}$替换, 故 x 也能由集合 B 得到

压缩后的集合性质

该集合与原集合等价(这里等价是指异或能够得到的值相等)且某一位作为最高位的数仍然唯一。

这样我们就能得到一个性质：
对于任意一个集合, 如果其中有两个元素的最高位相等,
可以用异或将其中一个元素替换, 如此下去, 可以让该集合用某一位作为最高位的数唯一
也就是说对于一个集合, 集合中每个元素的值小于$10^{\wedge} 18$,
该集合与一个大小为62的集合等价(因为集合中的元素顶多有62位,每一位作为最高位唯一)

一般来说，构建线性基常常采用动态插入元素的方法，即：不断地向已经得到的线性基里面加入新的元素，如果它可以被线性基内其他元素的组合异或出来，则舍去；否则留下。

vector<LL> B;
void insert(LL x) {
    for (auto b : B) x = min(x, b ^ x);
    for (auto &b : B) b = min(b, b ^ x);
    if (x) B.push_back(x);
}

异或第k小的数

LL query(LL k)
{
    LL ans = 0;
    if ((int)B.size() < n) k --;
    for (LL b : B)
    {
        if (k & 1) ans ^= b;
        k >>= 1;
    }
    if (k == 0) cout << ans << endl;
    else cout << -1 << endl;
}

sort(B.begin(), B.end());
query(k);

但是如果要处理bitset的话，这种做法就不是很方便，因为bitset不提供<操作符，而且即使手写出来也会导致复杂度增加。这时可以用相对传统的方法，用B[n]存最高有效位为n的元素，比如这样写：

bitset<N> B[N];
void insert(bitset<N> x)
{
    for (int i = 0; i < N; ++i)
        if (x[i])
            x ^= B[i];
    if (x == 0) return;
    int msb = N - 1;
    while (msb && x[msb] == 0) msb--;
    B[msb] = x;
    for (int i = msb + 1; i < N; ++i)
        if (B[i][msb])
            B[i] ^= x;
}

建立线性基和插入一个的操作

建立相当于是插入了。

for (int i = 1; i <= n; i ++)
{
    scanf("%lld", &tmp);
    lis.insert(tmp);
}

inline bool insert(ll x)
{
    for (int i = MAXN; i >= 0; --i)
        if (x & (1ll << i))
            if (b[i]) x ^= b[i];
            else
            {
                b[i] = x;
                return true;
            }
    flag = 1; //表示异或得到零
    return false;
}

注意：线性基中无法异或得到0，如果原集合可以异或得到0需要特判。

线性基的传统用法

异或最大值

ll get_max()
{
    ll ret = 0;
    for (int i = MAXN; i >= 0; -- i)
        if ((ret ^ b[i]) > ret)
            ret ^= b[i];
    return ret;
}

异或最小值

ll get_min()
{
    if (flag) return 0;
    for (int i = 0; i <= MAXN; i ++)
        if (b[i]) return b[i];
    return 0;
}

异或第k小

inline void rebuild()
{
    for (int i = MAXN; i >= 1; i --)
        if (b[i])
            for (int j = i - 1; j >= 0; j --)
                if (b[i] & (1ll << j))
                    b[i] ^= b[j];

    for (int i = 0; i <= MAXN; i ++)
        if (b[i])
            p[cnt ++] = b[i];
}

ll kth(ll k)
{
    if (flag)
        k --;
    if (k == 0)
        return 0;
    ll ret = 0;
    if (k >= (1ll << cnt))
        return -1;
    for (int i = 0; i <= cnt - 1; i ++)
        if (k & (1ll << i))
            ret ^= p[i];
    return ret;
}

线性基合并

L_B merge(const L_B &n1, const L_B &n2)
{
    L_B ret = n1;
    for (int i = 0; i <= MAXN; i ++)
        if (n2.b[i]) ret.insert(n2.b[i]);
    ret.flag = n1.flag | n1.flag; //特判是否能够异或处理
    return ret;
}

bitset维护线性基(牛客挑战赛59 C )

求一个集合的最大异或和子集，可以用线性基来做。

现在观察奇数个和偶数个的做法。可以对大于最长二进制数的最高位全部赋值为1，这样当求奇数个时，将将每一位赋值为0，因为0和1异或为1/和0异或为0，那么直接在原线性基上求最大即可（因为线性基是对原线性基的压缩）。当求取个数为偶数时，对一开始的基最高位赋1，这样只有在取偶数个时，最高位是1。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <algorithm>
#include <bitset>

using namespace std;

typedef long long LL;

const int MAXN = 2010;

bitset<MAXN> p[MAXN];

void insert(string &s)
{
    bitset<MAXN> x(s);
    x.set(MAXN - 1);
    for (int i = MAXN; i >= 0; i --)
        if (x[i])
        {
            if (p[i].count() == 0)
            {
                p[i] = x;
                break;
            }
            x ^= p[i];
        }
}

void get_max(bitset<MAXN> &ans)
{
    for (int i = MAXN - 1; i >= 0; i --)
        if (!ans[i]) ans ^= p[i];
}

void print(bitset<MAXN> &ans)
{
    int p = MAXN - 2; //去除最高位的1
    while (p && !ans[p]) p --; //去除前导零
    for (int i = p; i >= 0; i --)
    {
        cout << ans[i];
    }
    cout << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    string s;
    while (n --)
    {
        cin >> s;
        insert(s);
    }
    bitset<MAXN> c;
    //偶数 
    c.set(MAXN - 1);
    get_max(c);
    print(c);
    //奇数
    c.reset();
    get_max(c);
    print(c);
    return 0;
}