线性基

基本概念¶

请自学高中的线性代数，并基本掌握这些内容：

我们从代数上还可以说，多个标量捆绑在一起构成了向量（）

向量定义
代数表示
基本运算（代数与几何上）
- 数乘：乘以标量 \(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的二进制形式表出，在线性基中只考虑有值的位，直接根据二进制位选择即可。

https://www.luogu.com.cn/problem/P4151