线性基 | Caicz's blog

数学

基础学习

发布日期: 2020-08-27

阅读次数:

前言

线性基算是上周网课，都讲过的内容了，~~但网课时上的不认真~~现在才开始我的线性基学习

算法内容

线性基简介

线性基是一种擅长处理异或问题的~~数据结构~~数学工具(虽然有数据结构的许多性质，但参考 $OI-Wiki$ 将其划分到了数论板块)

线性基是向量空间的一组基，通俗一点将就是有一个集合构造出来的另一个集合，它满足这些性质:

线性基的元素能相互异或得到原集合元素的所有相互异或得到的值
线性基是满足性质1的最小的集合
线性基中没有异或和为 0 的子集
线性基中每个元素的异或方案唯一，也就是说，线性基不同的异或组合异或出的数据是不一样的
线性基中每个元素的二进制最高位互不相同

线性基的插入/构造

如果我们要插入的数为 $x$ ，我们判断 $x$ 的最高位 $i$ 在线性基中是否已经存在。

如果不存在，我们直接在当前位置上插入 $x$ 并退出
如果已经存在值为 $p_i$ ，则令 $ x=x\bigoplus p_i$ ,再重复判断直至 $x=0$

如果退出时 $x=0$ 则说明线性基已经可以表示原先的 $x$ 了；反之，则说明为了表示 $x$ ，我们往线性基中加入了一个新元素

这样的复杂度是 $\log_2x$ 的，我们也可以用这种方法判断是否能过通过原数列异或得到一个数 $x$

inline void insert(ll x)
{
    for(register int i=62;i!=-1;--i)
        if(x&(1ll<<i))
            if(!p[i]){p[i]=x;return;}
            else x^=a[i];
    minans=true;
}

inline bool check(ll x)
{
    for(register int i=62;i!=-1;--i)
        if(x&(1ll<<i))
            if(!p[i])return false;
            else x^=a[i];
    return true;
}

线性基查询异或最值

查询最小值相对比较简单。我们考虑插入的过程，因为每一次跳传操作中，$x$ 的二进制最高位一定严格单调递减，所以不可能插入两个二进制最高位相同的数。因此，线性基中最小值异或上其他值一定会增大，所以直接输出线性基中的最小值即可

考虑异或最大值，从高到低遍历线性基，考虑到第 $i$ 位时，如果当前的答案 $x$ 第 $i$ 位为 $0$ ，就将 $x$ 异或上 $a_i$ ；否则不做任何操作。显然，每次操作后答案不会变劣，最终的 $x$ 即为答案。

同样的，我们考虑对于询问某个数 $x$ 与原序列中的数的异或最值如何获得，我们用与序列异或最大值类似的贪心即可解决

inline ll qmin()
{
    if(minans)return 0;
    for(register int i=0;i<=62;++i)return p[i];
}

inline ll qmax(ll res=0)
{
    for(register int i=62;i!=-1;--i)res=max(res,res^p[i]);
    return res;
}