线性基学习笔记

基(basis)是线性代数中的一个概念,它是描述、刻画向量空间的基本工具。而在现行的 OI 题目中,通常在利用基在异或空间中的一些特殊性质来解决题目,而这一类题目所涉及的知识点被称作「线性基」。

以上描述引用自这位神犇的博文,讲解十分详细,我此处做一点简单的归纳。

先再贴两个链接:

[学习笔记]线性基

关于线性基的学习与理解

在OI中,线性基主要解决异或相关问题

如果你现在有一个数集,这个集合的每个非空子集中的值异或起来可以得到一些值,异或出来的这些值组成了一个集合

线性基就是一个极小的这个数集的子集,它的每个非空子集中的值异或起来得到的集合与原集合相同

线性基中存的数二进制依次排列可以参考以上例子,每一横行存的是一个二进制数。

构造线性基的方法就是从高位到低位贪心:

求某个值在所有线性组合中排第几以及线性组合中排第几的数的值直接枚举,线性基中第i个数前有\( 2 ^ {i} \)个数(这里暂时没讲清楚,可以选择性无视)。

具体内容链接到的神犇博客已经讲的很清楚了,此处不再细说。

以下贴题:

bzoj2115 Xor

bzoj2460 元素

bzoj4568 幸运数字

bzoj2844 albus就是要第一个出场

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注