线性基佐料

2008verser · 2023-12-31 16:13:19 · 算法·理论

2025: 两年前写的一篇。感觉很高质了。

【少图预警！】【需要结合其他文章食用！】

？声明？

这里不对线性代数相关概念和异或线性基做最基本的概述。

上网搜大概可以搜到三篇高质的讲解线性基的博客：

线性基小记 - command_block 的博客 - 洛谷博客 (luogu.com.cn)

线性基学习笔记 - 拜傅里叶教总部 - 洛谷博客 (luogu.com.cn)

线性基学习笔记 | Menci's OI Blog

下面两篇适合入门。上面那个没点线性代数基础感觉看不太懂。

最下面这一篇介绍的线性基构建方法比较麻烦。

它保证了每一个存在于线性基的位置 i，仅有 a_i 的第 i 位为 1。

但这个性质完全可以在构建完线性基后，扫一遍来完成。将在模板习题给出。

-

文章中习题包括但不限于 11251 号题单。

与其说一篇关于线性基的描述，不如算是对许多博客未加证明的结论的补充，或是隐藏的结论的点明。

速成顺序建议：【模板】【前缀】【实数】【CF1163E】。

-

线性基的性质，除了常说的，基最小、基线性无关、基的张成等于原集合的张成、原集合元素的唯一表示以外，还有很多，我们将在例题逐一分析。

读者注意留意题目中各种映射关系，有助于理解。

为防不知道有没有的读者和我用的循环压缩不一致，下面的代码默认有这两行 #define：

#define rp(i,r,l) for(int i=(r);i>=(l);--i)
#define fo(i,l,r) for(int i=(l);i<=(r);++i)

全文 w 定义为 \log V。

模板线性基：P3812 【模板】线性基

这里补充一个构造线性基时需要用到的结论，或有助理解：

• 将基中的任意一个元素异或上基中的另外一个元素，基仍是基。

证明考虑，设是 x 异或上了 y 变成 x'=x\oplus y，把原张成的每个含 x 的元素，替换成 x'\oplus y 即可。

根据「基的张成等于原集合的张成」，我们可以对输入的全部数求基。

那么问题变成了，我们在基里面选若干元素使异或和最大。

到这里，可以使用前两篇博客中的构造方法，写出这样的代码：

void insert(ll x) {
    rp(i,w,0) {
        if(x&(1ll<<i)) {
            if(!a[i]) { a[i]=x;return; }
            x^=a[i];
        }
    }
}
ll query() {
    ll ret=0;
    rp(i,w,0) if((ret^a[i])>ret) ret^=a[i];
    return ret;
}

但是这样丝毫不能体现我们对线性基的高超技艺。

我们可以使用第三篇博客的构造方法，这样构造出的基，如果第 i 位存在，那么第 i 列仅这一个为 1。（可以去 Menci 博客里好好看看，这里不详细讲）

也就意味着一个非零的行，我们选他，一定更优。

那么全部异或起来就对了。

事实上，Menci 博客里面的构造方式有些繁琐。我们可以按照前两篇博客的构造方式先构造一组线性基。

因为线性基里的数随便异或不会改变任何事情。我们可以不断异或，使得这组线性基具有 Menci 博客中提到的性质。如下：

void insert(ll x) {
    rp(i,w,0) {
        if(x&(1ll<<i)) {
            if(!a[i]) {
                a[i]=x;
                return;
            }
            x^=a[i];
        }
    }
}
void prepare() {
    fo(i,0,w) {
        rp(j,i-1,0) {
            if(a[i]&(1ll<<j)) a[i]^=a[j];
        }
    }
}
ll query() {
    prepare();
    ll ret=0;
    rp(i,w,0) ret^=a[i];
    return ret;
}

第二种方法，我们的 prepare() 操作就是 command_block 博客里提到的：“将三角基进一步消成对角基”。（虽然我也不知道这俩是啥。）

在执行完 prepare() 以后，我们的基就有 Menci 博客里介绍的全部性质了。

模板题到这里就结束了。时间复杂度，三角基是 O(n\log V)。消成对角基要多一个 \log V。

Code for this.

P3857 [TJOI2008] 彩灯

即，计算给定集合的张成与 \{0\} 的并的大小。

直接对原集合求张成大小是不会的。所以我们先求基。

根据「原集合元素的唯一表示」以及「基线性无关」，我们知道基的每个元素选，或不选，组合成的数于原数组的张成都是不重不漏的。

那么一共能组合出 2^k 次方个数。k 是基的大小。

零也会被统计到。

时间 O(mn)。

Code for this.

P4301 [CQOI2013] 新Nim游戏

首先我们要熟知经典 Nim 游戏的结论：当一个局面全部石子个数的异或和为零，必败。否则必胜。

在这道题中，第一回合我们需要拿走若干堆石子，使得无论对手取哪几堆石子，都会送我们一个必胜局面。

也就是说，使得对手不能将局面变为，全部石子个数异或为零。

也就是说，我们拿完第一次，剩下的石子不存在一个非空的子集（因为对手可以不拿，所以不是真子集），使得异或和为零。

也就是说，剩下的石子线性无关。

注意基的定义，基没有异或和为零的子集。

且，「基，是原集合全部线性无关子集中，集合大小最大的」。

因为我们要最小化第一回合我们取的石子数量，所以剩下的石子要大。那么我们留一个基就好了。

为了最大化基，我们降序排序，顺序枚举，能选就选。

如果向 a_{1\to i-1} 形成的基中加入 a_i，变得线性相关，说明 a_i 可以被 a_{1\to i-1} 一些表示出来。

此时我们要么保留原本的基，要么从原本的基删掉一个元素，加入 a_i。

注意到，这两种基都是由 a_{1\to i-1} 形成的基，张成一样。即完全等价。

那么，对于两种等价的基，我们保留原本的基，答案不会更劣。

所以这是对的。

这种，「选取线性无关子集，最大化求和」或是「留下线性无关子集，最小化选取求和」的问题，以后还会遇到很多次，都可以用这种方式解决。

时间 O(k\log V)。

Code for this.

P4570 [BJWC2011] 元素

做过【P4301】这道题就算裸了。请读者自行完成。

P3292 [SCOI2016] 幸运数字

若我们得到两点间的线性基，事情就很典了。

注意线性基大小是 \log V 级别的。那么我们可以通过把一个线性基里的数加入另一个完成时间为 O(\log^2V) 的合并。

那我们有两种方法：

• 获得 (x,lca) 和 (y,lca) 的线性基，合并。
• 树剖+线段树或者倍增维护线性基。

询问是不确定的，所以第一种方法不行。（可以使用前缀线性基 O(q\log^2V)，但这里先不提前介绍）

从线段树询问区间线性基，会拆成 \log n 个区间，合并这些要 \log^2V\times\log n。

树剖需要 \log n 次线段树询问。所以时间是 O(q\log^2V\log^2n) 的。

注意线性基是可重复贡献的。可以用 ST 表维护某个点向上 2^i 的线性基。O(n\log^2V\log n+q\log ^2V)。