<span>线性基小记</span>

什么是线性基

线性基大概可以理解为对于一组数 \(A_1,A_2...A_n\) ，构造出一个大小为 \(\text{O}\left(\log_2\text{N}\right)\) 的一个数组 \(P\)（\(\text{N}\) 即为数组 \(A\) 中数的值域），使得数组 \(A\) 中的任意数都可以由数组 \(P\) 中的数异或得出。

在满足此条件时，线性基的大小应该尽可能的小。

线性基的性质

1. 数组能通过数组 \(A\) 中的数异或得出的数同样能够通过数组 \(P\) 中的数异或得出。

   • 线性基能表示出数组的所有数，所以一定可以表示出数组中数的异或值

2. 线性基中的每一个数在二进制形式下的最高位都不同。

   • 如果线性基中有两个数在二进制形式下的最高为相同，那么显然这两个数可以合并为一个数。

3. 线性基没有异或和为 \(0\) 的子集。

   • 如果线性基的某些数的异或和为 \(0\)，那么这些数中的某一些数的异或和一定等于另一部分的异或和，也就是说这两部分有一部分是多余的，所以必须舍去。

线性基的构造

设 \(P_i\) 为线性基中在二进制下最高位为 \(i\) 的数的值

每插入一个数 \(x\)，就执行一遍下面的操作：

• 从高到低枚举二进制下的位数 \(i\) ，如果线性基中最高位为 \(i\) 的数即 \(P_i\) 还没有数存入，就把 \(x\) 存入 \(P_i\) ，完成插入。

• 如果线性基中最高位为 \(i\) 的数已经存在，那么 \(x=x \ \oplus\ P_i\)

• 如果 \(x\) 为 \(0\) ，完成插入。

Code

void build()
{
    x=read();
    for(int i=50;i>=0;--i)
        if(x>>i)
        //如果 x 的前 i 位没有 1，那么下面的操作就没有意义 
        {
            if(!p[i])
            {
                p[i]=x;
                break;
            }
            x^=p[i];
        }
}

为什么这么做可以构造出线性基？

如果找到了一个没有存入任何数的 \(P_i\)，那么把 \(x\) 存入后就可以直接表示出 \(x\)。

如果找到了一个已经存入数的 \(P_i\)，那么只要线性基能表示出 \(x\ \oplus \ P_i\) 那么 \(x\) 就可以通过 \(P_i\ \oplus\ \left(x\ \oplus\ P_i\right)=x\) 表示出。
而如果 \(x_{(2)}\) 的第 \(i\) 位为 \(1\)，那么由于 \(P_i\) 的第 \(i\) 位一定为 \(1\) ，所以两数异或后 \(x\) 的第 \(i\) 位一定为 \(0\)，这样一位一位地做，最终肯定会使 \(x\) 变为 \(0\)。

线性基的复杂度

我们需要一个大小 \(\text{O}\left(\log_2\text{N}\right)\) 的数组来存储所有的 \(P_i\)，故空间复杂度 \(\text{O}\left(\log_2\text{N}\right)\)。

每插入一个数要遍历一边 \(P\) 数组，故时间复杂度也是 \(\text{O}\left(\log_2\text{N}\right)\)。

非常优秀

线性基的应用

求一组数中取任意数能得到的异或最大值

因为在原数组中异或得到的数也能在线性基中异或得到，所以问题就转换成了在这组数的线性基中找到异或最大值。

我们可以从高到低枚举位数 \(i\)，记 \(ans\) 为当前能得到的异或最大值，则如果 \(P_i\ \oplus\ ans>ans\)，那么就令 \(ans=P_i\ \oplus\ ans\)。

因为 \(P_i\) 的第 \(i\) 位为 \(1\)，如果 \(ans\) 的第 \(i\) 位为 \(0\)，那么异或后 \(ans\) 的第 \(i\) 为就变成了 \(1\)，即使后面几位再小，\(ans\) 也会变大，所以异或更优。

而如果 \(ans\) 的第 \(i\) 位为 \(1\)，那么异或后 \(ans\) 的第 \(i\) 为就变成了 \(0\)，即使后面几位再大， \(ans\) 也会变小，所以不异或更优。

因为是从高位到低位计算的，所以后面位数的计算不会影响前面位数的计算，所以是最优的。

Code

int getmax()
{
    int ans=0;
    for(int i=50;i>=0;--i)
        if((ans^p[i])>ans)
            ans^=p[i];
    return ans;           
}

最小值同理。

判断一个数能否通过一组数中任意数异或得到

假如判断的数是 \(x\) 那么从高到低枚举 \(x\) 的每一位，如果第 \(i\) 位为 \(1\)，那么就把它异或上 \(P_i\)，如果枚举完后 \(x\) 为 \(0\)，那么就可以表示出。

证明同理插入证明。

Code

bool check(int x)
{
    for(int i=50;i>=0;--i)
        if((x>>i)&1)
            x^=p[i];
    return x==0;
}

例题

Luogu P3812 【模板】线性基

<button class="accordion">Luogu P3812 【模板】线性基 解析

Luogu P3857 [TJOI2008]彩灯

<button class="accordion">Luogu P3857 [TJOI2008]彩灯 解析

Luogu P4570 [BJWC2011]元素

<button class="accordion">Luogu P4570 [BJWC2011]元素 解析

Atcoder ABC141F Xor Sum 3

<button class="accordion">Atcoder ABC141F Xor Sum 3 解析

待更新。。。

Ps：文章内容均为个人理解，如有错误欢迎指出。