线性基
基本概念¶
请自学高中的线性代数，并基本掌握这些内容：
我们从代数上还可以说，多个标量捆绑在一起构成了向量（）
- 向量定义
- 代数表示
- 基本运算（代数与几何上）
- 数乘：乘以标量 \(k\)，若为负数则方向相反，其长度变为原来 \(|k|\) 倍。
- 加（减）法：平行四边形法则。
- 其实向量还有内积和叉积，但与本节关系不大，暂略。
-
平面、空间向量基本定理，即基底的思想
-
线性空间：由一群可缩放和相加的数学实域（如实数甚至是函数）所构成的特殊集合，其特殊之处在于缩放（e.g. 数乘）和相加后仍属于这个集合（封闭）。不严谨的讲，只要能满足这两种运算封闭的数学对象（广义的向量）构成的集合，都可以称作 “线性空间”。
- 线性组合：即向量与数乘、加法的任意组合。
- 线性无关：线性空间的一组向量中，若没有向量可由该组中有限个其他向量的线性组合所表示，则称它们线性无关或线性独立。比如一组基底就是线性无关的。
实数线性基¶
二维与三维的实数线性基，其实就是平面空间和立体空间的一组基底。
异或空间线性基¶
我们知道，对于每一个二进制位来说，异或是模2意义下的封闭加法运算。根据取模意义下的乘法，我们也可以得出其在模2意义下运算封闭。这是什么？这是线性空间！！！
那么，若把数字的每一个二进制位看成一个标量，则数字便是把它们“捆”起来的一个“向量”，其二进制位个数类似于维数。
用处¶
- 快速查询一个数是否可以被一堆数异或出来
- 快速查询一堆数可以异或出来的最大/最小值
- 快速查询一堆数可以异或出来的第k大值
- 查询一个数异或一堆数中任意个的最大值
求法¶
高斯消元求线性基¶
#include <bits/stdc++.h>
using ull = unsigned long long;
const int MAXN = 1e5 + 5;
ull deg(ull num, int deg) { return num & (1ull << deg); }
ull a[MAXN];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%llu", &a[i]);
int row = 1;
for (int col = 63; ~col && row <= n; --col) {
for (int i = row; i <= n; ++i) {
if (deg(a[i], col)) {
std::swap(a[row], a[i]);
break;
}
}
if (!deg(a[row], col)) continue;
for (int i = 1; i <= n; ++i) {
if (i == row) continue;
if (deg(a[i], col)) {
a[i] ^= a[row];
}
}
++row;
}
ull ans = 0;
for (int i = 1; i < row; ++i) {
ans ^= a[i];
}
printf("%llu\n", ans);
return 0;
}
贪心法求线性基¶
贪心+消元的动态方法*¶
增删改查¶
验证线性相关¶
只需要看能否最终插入线性基即可。
从中取任意多个数，与某个数异或的最值¶
贪心
能异或出的第 k 大值¶
先消成最简形式，即主元有且仅出现一次。
将k的二进制形式表出，在线性基中只考虑有值的位，直接根据二进制位选择即可。