线性基

发表于 2023-05-08 更新于 2025-08-09 分类于程序设计竞赛

线性基

异或的性质

预备知识-奇妙的异或运算

异或的性质：
如果\(c == a \land b\)
则有：\(a \land c == b\) 和 \(b \land c == a\)
执行以下3条操作的效果是？
\(a = a \land b\)；\(b = a \land b\)；\(a = a \land b\)；
答案：整数a和b的交换 ### 例题：
给出\(2n{+}1\)个整数，除\(1\)个数外，其余\(2n\)个数均成对出现，请编程找出这个单独的数；
有\(n{+}1\)个数组成的数列，包含\(1\)-\(n\)这\(n\)种整数，也就是说，有一个数是重复出现的，求其值；
给出\(2n{+}2\)个整数，除\(2\)个数外，其余\(2n\)个数均成对出现，请编程找出这\(2\)个不成对的数；

导引问题

给出n个数：\(a_1,a_2,\dots,a_n\)，请问：

取其中的一些数进行异或操作，能否得到值\(Q_X\)？

线性基定义

对于一个数集A，它的线性基是一个最小的数集B，使得A中任意一个数可以通过B中的一些数异或得到。

对于一个数集，它可能存在不止一个线性基，且这些线性基都是等价的。

在某些涉及异或的操作中，线性基可以代替原集合，从而达到减小数据规模的目的。

eg. 线性基举例

对于一个集合A：{4，5，6}

它的线性基可以是： 1. {6,1,2} 2. {4,1,2} 3. {5,1,3} ……

构造线性基

如何求线性基

观察线性基与目标序列的关系：

如 4,5,6

6	→	110
5	→	101
4	→	100

通过线性代数的知识，求出极大线性无关组

	异或化简
110	\(\longrightarrow\)	100
101		010
100		001

如何求线性基：线性基的关键在于降低规模
若 \(X = a_{i1} \text{^} a_{i2} \dots \text{^} a_{ik}\)，则意味着 \(X\) 可被其他已选的数表示，所以就去掉 \(X\)（不把 \(X\) 当做线性基元素）；

思考：为什么要使求得的线性基最高位不同？
理由：便于计算出 \(X\) 是否能被现有的数表示。

线性基的形式：

\(a[1]{=}1XXXXX\)
\(a[2]{=}01XXXX\)
\(a[3]{=}0001XX\)
……

为了方便，设置\(d[i]\)表示非0最高位为右数第\(i\)位的数 \(d[5]{=}1XXXXX\)
\(d[4]{=}01XXXX\)
\(d[2]{=}0001XX\)
### 求解代码

对于序列\(a_1, a_2, \dots, a_n\)

long long d[61];//记录确定第i位的数d[i] 初始值为0
for(int i=1;i<=n;i++) //考虑每一个数
{
    long long x=a[i];
    for(int j=60;j>=0;j--) //逐位确定
        if(x&(1LL<<j))  //只有该位为1的时候才考虑，且此时更高位都为0
        {
            if(d[j]==0) //当这一位没有被确定时
            {
                d[j]=x;
                break;
            }
            else x^=d[j]; //通过异或操作将这一位的1去掉
        }
}

最后得到的有值的d[]就是所求的线性基，这样储存操作更为方便

线性基性质

线性基没有值为0的元素；
线性基元素中任意一个都无法通过另外的线性基元素异或得到；
原集合中的任意一个数都可以通过线性基中的某些数异或得到；

导引问题解答

给出n个数：\(a_1, a_2, \dots, a_n\)，请问：取其中的一些数进行异或操作，能否得到值\(Q_x\)？

如何解决？

求解线性基，看是否可以消去

算法思想：
1. 将这n个数求出线性基 \(d[]\)
1. 将询问的值\(Q\_x\)通过该线性基，若\(Q\_x\)经过线性基后为0则表示\(Q\_x\)可以被表示，否则无法被表示。

bool check(long long x) //与将数插入线性基中同样的方法
{
    for(int j=60;j>=0;j--)
    if(x&(1LL<<j))
    {
        if(d[j]==0)
        {
            return false; //若此时这一位没有被一个线性基里的数确定，则该位的1不能再被消除
        }
        else x^=d[j];
    }
    return (x==0); //一个数插入线性基得到0，说明这个数可以被这个线性基表示
}

例题1-求最大异或值

给出n个数，\(a_1\),\(a_2\),…,\(a_n\) ，问取其中的一些数进行异或操作，能够得到的最大的数是多少。
请思考并回答～
1. 将这n个数求出线性基 \(d[]\)
1. 将答案初始化为0
1. 从高位到低位查询，若当前答案该位(第i位)为0且 \(d[i] \neq 0\)，则当前答案异或 \(d[i]\)
1. 所有位查询以后得到的答案就是最大值

long long find()
{
    long long ans=0;
    for(int i=60;i>=0;i--)
    {
        if(((1LL<<i)&ans)==0&&d[i])
            ans^=d[i];
    }
    return ans;
}

例题2-异或最小值

算法思路：

将这n个数求出线性基d[]；
在构造线性基的过程中，若存在一个数插入线性基时插入失败，即插入后x=0，那么最小值为0；
若答案不为0，则答案为最小可确定位所表示的d[i]。即：从低位往高位看，如果一个位置的d[i]不为0，则答案就是该d[i]。

例题3-异或第k小值

给出n个数，a1,a2,…,an，问取其中的一些数进行异或操作，能够得到的第k小的数是多少（去重过）。

思考并回答~

解题思路：
将这n个数求出线性基 \(d[]\)（最简单形式）。
观察 \(d[]\)，我们只能在 \(d[i] != 0\) 时，自由选择第i位为0或者为1。
由于线性基无法异或出0。特判是否会出现异或为0的情况，若出现则 \(k = k - 1\)。
对于能够选择的位，我们可以确定0或者1。那我们将k二进制表示，若某一位为0，则将可选择位的值置为0，否则置为1。
代码思路： 我们从d的下标0开始往上找到第一个不为0的线性基，如果k这一位是1，就把找到的对应的线性基异或进答案，否则就不异或进去。然后k整除2，继续这一过程。
假设有两个数2和8，k=2时答案显然是8，求解过程如下：
首先，\(d[1]=2\)，\(d[3]=8\)
k是2（二进制10），我们找到的第一个非0线性基是\(d[1]=2\)，但是k末尾是0，就不异或到答案里，然后继续找到的是\(d[3]=8\)，k接下来一位是1，就异或到答案里面去，所以答案是8。

需要化简为最简的线性基

本讲主要内容

线性基的定义

给定数列求线性基

求异或最大值

求异或最小值

求异或第K小值