首页 > 学习线性基,这一篇就够了!
头像
明天也不想努力
发布于 2021-05-25 15:14
+ 关注

学习线性基,这一篇就够了!

前言

这些东西有助于你了解线性基。

线性基是一种简洁有效的数据结构,一般用于解决异或和/最大值/第K大等问题。
常用的线性基一般是定义在模2意义下(大部分为异或空间)中的。
本文旨在以不那么深奥的方式解释这个数据结构。

基础概念

这些东西有助于你理解线性基。

1. 张成子空间(span)

百度百科链接

,所有子集 的异或和组成的集合即为 张成的子空间,记作 。通俗解释就是在 中选任意多个数,所有可能的异或和组成的集合。

异或空间下的定义即为用集合中的数可以异或出的数组成的集合。

2. 向量空间(vector space)

以下内容摘自百度百科 [1]

向量空间亦称线性空间。它是线性代数的中心内容和基本概念之一。设V是一个非空集合,P是一个域。若:

1.在V中定义了一种运算,称为加法,即对V中任意两个元素α与β都按某一法则对应于V内惟一确定的一个元素α+β,称为α与β的和。

2.在P与V的元素间定义了一种运算,称为纯量乘法(亦称数量乘法),即对V中任意元素α和P中任意元素k,都按某一法则对应V内惟一确定的一个元素kα,称为k与α的积。

3.加法与纯量乘法满足以下条件:

1) α+β=β+α,对任意α,β∈V.

2) α+(β+γ)=(α+β)+γ,对任意α,β,γ∈V.

3) 存在一个元素0∈V,对一切α∈V有α+0=α,元素0称为V的零元.

4) 对任一α∈V,都存在β∈V使α+β=0,β称为α的负元素,记为-α.

5) 对P中单位元1,有1α=α(α∈V).

6) 对任意k,l∈P,α∈V有(kl)α=k(lα).

7) 对任意k,l∈P,α∈V有(k+l)α=kα+lα.

8) 对任意k∈P,α,β∈V有k(α+β)=kα+kβ,

则称V为域P上的一个线性空间,或向量空间。V中元素称为向量,V的零元称为零向量,P称为线性空间的基域.当P是实数域时,V称为实线性空间.当P是复数域时,V称为复线性空间。例如,若V为三维几何空间中全体向量(有向线段)构成的集合,P为实数域R,则V关于向量加法(即平行四边形法则)和数与向量的乘法构成实数域R上的线性空间。又如,若V为数域P上全体m×n矩阵组成的集合 ,V的加法与纯量乘法分别为矩阵的加法和数与矩阵的乘法,则 是数域P上的线性空间.V中向量就是m×n矩阵。再如,域P上所有n元向量(a1,a2,…,an)构成的集合P对于加法:(a1,a2,…,an)+(b1,b2,…,bn)=(a1+b1,a2+b2,…,an+bn)与纯量乘法:λ(a1,a2,…,an)=(λa1,λa2,…,λan)构成域P上的线性空间,称为域P上n元向量空间。

简单讲就是一个包含向量加法和标量乘法(数乘运算)的封闭向量集合。

若这个线性空间推广为一个异或空间,那么就是一个关于异或运算的封闭的集合,零元为 为非负整数域。

3. 线性相关和线性无关(linearly dependent & linearly independent)

对于一个线性空间中的若干个向量,如果存在一个向量可以被除它以外的向量标出,即称这些向量线性相关,否则称这些向量线性无关

异或空间下线性相(无)关即为(不)存在一个数可以被除它以外的数异或出。

4. 线性基(linear basis)

一个线性空间张成的线性无关子集被称为线性空间的基底,简称
另一种基的定义方式是线性空间的极大线性无关子集。一个线性空间可以有多个基,但所有基内的向量个数(称为“维数”)都相等

举个小栗子:
对于一个立体空间,它的所有向量构成一个三维线性空间。 就是它的一个基。

另一个经典的例子就是二维平面直角坐标系。
如图, 分别是坐标系的单位向量,即基向量。

pic

那么,将向量 反向拉升为原来的 倍,向量 拉升为原来的 3 倍,即可表示出一个新的向量

pic

同理,坐标系中的向量都可以通过缩放/加减基向量得到。

基向量的选择也可以多种多样,如图:

pic

亦可表示出一些新的向量。

pic

5. 秩和拟阵(rank & matroid)

秩·百度百科链接

通俗地讲即是一个矩阵的行/列秩即是其线性独立的行/列的极大数。
用初等行变换把原矩阵变换为阶梯型矩阵,非零的行数即为矩阵的秩。

初等行变换(百度百科链接)即是 用一个非零的数乘某一方程;把某一方程的倍数加到另一个方程;互换两个方程的位置 三个操作的合称。

这有个某帮上的栗子。
对于矩阵:

1 1 2 2 1
0 2 1 5 -1
2 0 3 -1 3
1 1 0 4 -1

我们将其变换为:

1 1 2 2 1
0 2 1 5 -1
0 0 0 0 0
0 0 1 -1 1

故秩为

拟阵·百度百科链接

拟阵可以用于证明大部分贪心算法的正确性,而线性基有一个重要性质:用线性基解决的问题大多可以按位贪心
这条性质亦可以用拟阵来证明。可是我太菜了,不会证。而且同是 OIer 你要证什么明。
关于拟阵证明贪心算法的基础学习可以参考:

刘桂真, 陈庆华. 拟阵[M]. 长沙: 国防科技大学出版社, 1994

呐,其实我们可以感(自)性(欺)理(欺)解(人)一下。异或运算只和当前位有关系,所以我们一定会要求最大位尽可能地大/小。
不就是个贪心嘛。

线性基的性质

  1. 能被线性基集合中的某个子集的异或和得到,该子集唯一

  2. 线性基集合中任意一个子集的异或和

  3. 线性基集合中每个元素的最高位互不相同

  4. 若线性基集合中存在最高位为 的数,它的异或集合为

这些性质都较显然,结合定义和构造方法即可理解。

线性基的操作

数组存储线性基的元素。

1. 插入

插入操作的本质就是在高斯消元。
如果是预处理的话,将每个数二进制展开,将高斯消元的加法换为异或即可。
同理,可得在线算法的过程:

插入数 时:
① 从高到低扫描它为 的二进制位。
② 扫描到第 位时,如果 不存在,就令 ,否则
③ 最后, 要么被插入线性基,要么变成

bool Insert(int x)
{
    for(int i=MAX_LIM;~i;i--)
        if(x&(1<<i))
            if(!p[i]) return p[i]=x,1;
            else x^=p[i];
    return 0;
}

2. 查询最大值/最小值

查询最大值时:从高到低扫描,对于 取最大值即可。

int AskMax()
{
    int res=0;
    for(int i=MAX_LIM;~i;i--) res=max(res,res^p[i]);
    return res;
}

查询最小值时:取最小的一个存在的 即可。

int AskMin()
{
    for(int i=MAX_LIM;~i;i--)
        if(p[i]) return p[i];
    return 0;
}

有一些题目可能会询问一个数 在线性基内可以异或出的最大值/最小值。此时只需将 的初始值改为 即可。

3. 查询第

这时一般线性基就原地爆炸了。
为什么?
因为对于一个这样

101
001

的线性基,选第一个和第二个比只选第一个差。

那么如果这个线性基可以变成这个样子,

100
001

选第一个和第二个比只选第一个优,就变得可做了。
所以我们只需要对于 的第 位为真的 操作,即可使第一种线性基转变为第二种线性基。

int k0=0;
void Setup()
{
    for(int i=MAX_LIM;~i;i--)
        for(int j=i-1;~j;j--)
            if(p[i]&(1<<j)) p[i]^=p[j];
    for(int i=0;i<=MAX_LIM;i++)
        if(p[i]) kt[k0++]=p[i];
}

那么查询时只需对于 的每一位都异或 即可。
但是,如果线性基可能构造出 ,则需要给

bool Insert(int x)
{
    for(int i=MAX_LIM;~i;i--)
        if(x&(1<<i))
            if(!p[i]) return p[i]=x,1;
            else x^=p[i];
    return ri=1,0;
}
int Kth(int k)
{
    k-=ri;
    if(k>>k0) return -1;
    int res=0;
    for(int i=k0-1;~i;i--)
        if(k&(1<<i)) res^=kt[i];
    return res;
}

4. 查询 的排名

方法1:二分法
时间复杂度 ,直接二分 是否等于 即可。

int Binary_Search(int x)
{
    int l=0,r=1<<MAX_LIM;
    while(l<=r)
    {
        int mid=(l+r)>>1,tmp=Kth(mid);
        if(tmp<x) l=mid+1;
        else if(tmp>x) r=mid-1;
        else return mid;
    }
    return -1;
}

方法2:

没有名字就乱取了个。
顾名思义,套用查询第 小的 操作,同时开一个 存储当前累加的排名。
注意此时 存的是第 个有值的 下标,即
从后往前扫 数组,如果 的第 位为真,则这一位为假时前面的 位随便怎么取都会比 小,所以 需要加上
如果 最后 ,则线性基集合与 线性无关。
是一个比较好理解的算法,若不理解可以手玩下面这组栗子:

线性基数组p:
p[0]=1,p[1]=2,p[3]=0,p[4]=8
可以异或出的数:1,2,3,8,9,10,11
求10的排名。
10的第3位为真,那么所有第3位为假的数(0,1,2,3)都要被算入答案;
10的第1位为真,那么所有第1位为假(但第3位为真)的数(8,9)都要被算入答案。
特判0的情况,故10的排名为6。

仍需特判能否构造出 的问题。下面的代码并没有考虑这个问题。

int Rank(int x)
{
    int res=0;
    for(int i=k0-1;~i;i--)
        if(x&(1<<kt[i])) res+=1<<i,x^=p[kt[i]];
    return x?-1:res;
}

5. 合并两个线性基

暴力插入。

void Merge(int *p1,int *p2)
{
    for(int i=MAX_LIM;~i;i--)
        if(p2[i]) Insert(p1,p2[i]);
}

6. 线性基求交/并

本质是线性空间求交/并。

小拓展

一道很有意思的题,为 Atcoder ZONe Energy Programming Contest 最后一题,题目链接。读者不妨自行思考。

另外,亦可思考其与高斯消元法的联系。

结语

本文因作者才疏学浅,难免有不足之处。若有任何问题,希望大家不吝赐教。
看了这么多,点个赞或收藏下再走吧。

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐