线性基模板

线性基

定义

根据oiwiki， 线性基是一个集合(整数序列)构造出的另一个集合， 这个新集合满足一下性质

1. 线性基的元素相互异或能够得到所有原集合元素能够异或出来的值
2. 线性基是满足性质1的最小的集合
3. 线性基没有异或为$0$的子集
4. 每个原集合能够异或出的元素在线性基中的异或方式是唯一的
5. 线性基内每个元素的最高二进制位互不相同

求法

代码

我们采用插入数值的方法， 遍历原集合的每个元素尝试插入线性基中

long long al[51]; // 线性基中最高二进制位为i的元素

void Insert(long long x)
{
    for(int i = 50; i >= 0; i --)
    {
        if(! ((1LL << i) & x)) continue;

        if(al[i])
            x ^= al[i];
        else
        {
            al[i] = x;

            break;
        }
    }
}

证明

当我们要插入一个数$x$时， 考虑到性质3， 我们先尝试把$x$和已有的线性基元素异或看看时候能把$x$变为$0$， 也就是看$x$能不能由当前已有的线性基异或得到， 如过能够做到， 那$x$不需要被加入线性基； 否则， 由于我们在这一过程中尝试将$x$异或成$0$，$x$是在变化的， 如果从高到低遇到一位无法被异或掉， 考虑性质$1$， 我们要想异或出原来的$x$那就必须要把剩下的这个$x$加入线性基， 而这也恰好能满足性质5

对于性质1和性质4： 刚才我们已经证明了原集合中的每个元素都可以被线性基表示， 那么假设原集合为$X$， 线性基为$Y$， 有一个元素$S = X_{a_1} \oplus X_{a_2} \oplus … \oplus X_{a_k}$， 表示$S$是由原集合的$k$个元素异或得到的， 由于每个$X_i$都可以由线性基中的元素异或得到， 那我们统计这$k$个元素中每个线性基元素的使用次数， 将所有使用次数为奇数的线性基元素异或起来就得到了$S$

对于性质2， 由性质5可以自证

典型应用 + 代码

给$n$个元素， 求其中元素能异或出的最大值

#include <iostream>
#include <cstdio>

int n;
long long al[51];
long long ans;

void Insert(long long x)
{
    for(int i = 50; i >= 0; i --)
    {
        if(! ((1LL << i) & x)) continue;

        if(al[i])
            x ^= al[i];
        else
        {
            al[i] = x;

            break;
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        long long a;
        scanf("%lld", &a);

        Insert(a);
    }

    for(int i = 50; i >= 0; i --)
        if((ans ^ al[i]) > ans)
            ans ^= al[i];

    printf("%lld\n", ans);

    return 0;
}