算法笔记：线性基详解

线性基是一个听起来很高级但实际上还蛮简单的算法，本质就类似于线性代数中的基向量，是一个整数集合的一组线性无关的数字。说是算法，我觉得其更偏向是一种思想。

例如一组向量：

v1={1, 0, 0}

v2={0, 1, 0}

v2={0, 0, 1}

三者中任意一个都无法用另外两者表示出来，因此它们线性无关。

举个线性基的例子(以下为二进制表示)：

对一个整数集合{101, 100, 010, 011, 001}求线性基得到

{101, 010, 001}（这也是一组数不是向量啊

线性基三者中任意一个都无法通过另外两者异或得到，且原集合中的任意一个数都可以通过线性基中的某些数异或得到。

求线性基的过程如下：

ll lb[61];//线性基，大小取决于数字值域
int inse(int x)//将x插入线性基，插入成功返回1，否则返回0
{
    //每次找到x的最高位的1
    //若线性基这个位置还没有数字，则把x插入这里
    //否则用线性基中这个位置的数字异或x，继续找x最高位的1
    for (int i=60; i>=0; i--)//i的初值取决于数字的值域
    {
        if (!(x&(1ll<<1))) continue;
        if (!lb[i]) {lb[i]=x; return 1;}
        x^=lb[i];
    }
    return 0;
    //可以看出，线性基中位置在i的数字的二进制第i位（从右往左数）一定是1
    //更大的二进制位置一定是零，这样就保证了线性基中的数字都是线性无关的
}

ll num[101];//整数集合
for (int i=1; i<=100; i++)
    inse(num[i]);//将整数集合中的数字逐一插入线性基

线性基的一般是用来判断是否可以从一个整数集合中选取一个子集，子集中的整数异或得到某一特定数字。（用向量来比喻就是给你一些向量，是否能够用这些向量表示出某一特定向量）。

一般来说，线性基有三大性质：

1、原集合里面的任意一个数都可以由线性基里面的一些数异或得到，可以通过原集合中某些数异或出来的值，也可以通过线性基中某些数异或得到

2、线性基中任意一些数字异或起来不为0（补充：若一个数字K没有成功插入线性基，则说明线性基中的某些数字可以异或得到K

3、线性基的任意两个不同的子集，子集中所有数字异或起来的结果不同

4、线性基是满足以上性质的最小集合

关于线性基的一些基本操作，还有如何支持删除（之前插入的数字），这个大佬的博客里写的非常清楚：

关于线性基的删除操作，我再补充一点点。

还有一些例题及题解，明天再补orz

算法笔记：线性基详解

原文：https://www.cnblogs.com/opppppppp/p/12630002.html