线性基

线性基讲解

---

title: 线性基学习
author: Sun-Wind
date: July 7，2022

刷题时遇到的不会的知识点，顺便整理学习一下

线性基的定义

线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数

由此可见，线性基是用来解决子集异或一类题目的算法。

线性基的性质

• 原序列里面的任意一个数都可以由线性基里面的一些数异或得到
• 线性基里面的任意一些数异或起来都不能得到 0
• 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

线性基的构造

考虑构造一个数组s表示线性基，s[i]表示最高位————第i+1位为1的数

构造一般是如下步骤

• 遍历原集合中的每一个数，对于其中一个数设为a
• 逆序遍历a二进制表示中的每一位，如果遍历到第i位为1，则分两种情况处理
• 第一种情况 s[i] = 0;则 s[i] = a; a加入线性基，循环结束
• 第二种情况 $$ s[i] \neq 0$$ 则 a = a ^ s[i]消掉a第i+1位的1，继续如上循环

如果不是逆序则不满足s[i]表示最高位————第i+1位为1的数的条件

经过以上步骤可以构造出一个线性基s。

线性基一些性质的证明 第一性质证明

根据异或的可逆性质，如 a ^ b = c; 则 c ^ b = a;

在上述构造的过程中，如果一直出现第二种情况，最后a变成0，根据可逆性质可知，s中的数可以通过异或运算得到a，所以a不能加入线性基

否则，该数可以加入线性基。

根据可逆性质可知，线性基中的数可以表示出原集合里的任何数。

第二性质证明

利用反证法，若a ^ b = 0,则 a = b;
也不满足s[i]表示最高位————第i+1位为1的数的条件
由此得证

第三性质的证明

可以参考线性基详解

线性基代码

void add(ll x)
{
    for(int i=60;i>=0;i--)//逆序遍历
    {
        if(x&(1ll<<i))//如果第i+1位为1
        {
            if(d[i])x^=d[i];//消去第i+1位的1，继续循环
            else
            {
                d[i]=x;
                break;//插入成功就退出
            }
        }
    }
}

应用

最常见的应用————异或和最大问题

完整的说，是如何求在一个序列中，取若干个数，使得它们的异或和最大。

依然是构造出这个序列的线性基，由于线性基的值域和原序列相同，所以原序列中取数的问题就转换为从线性基中取数的问题

贪心的解法

从最高位考虑，如果ans和线性基异或的结果比ans还要大，说明第i+1位有贡献，并且这一步是最优的贡献

如果不从最高位考虑，则不是最优的贡献，可以找到更优的解

由该最优子结构则可以推出原问题的最优解

代码如下

ll ans()
{
    ll anss=0;
    for(int i=60;i>=0;i--)//记得从线性基的最高位开始
    if((anss^d[i])>anss)anss^=d[i];
    return anss;
 }   

这里的学习仅代表个人的浅见，如有建议欢迎提出
完结撒花★,°:.☆(￣▽￣)/$:.°★ 。