线性基⚓︎

线性基（ $\text{Linear Basis}$ ）是一种用于处理向量空间中线性无关向量集合的数据结构。它可以用于解决一系列与线性代数相关的问题，如求解线性方程组、计算向量的秩、寻找最大异或子集等。
线性基是一个向量组，可以表示该向量组中任意向量的线性组合。线性基的主要特点是其向量之间线性无关，即没有一个向量可以表示为其他向量的线性组合（线性无关性）。线性基的大小等于该向量组的秩。
线性基的时间复杂度通常为 $O(n \cdot m)$ ，其中 $n$ 是向量的维度， $m$ 是插入的向量数量。

普通消元⚓︎

普通消元法通过逐步消去向量中的最高位来构建线性基（贪心构造）。
该方法可以求出线性基的最大异或和、最小异或和、秩、能表示的数的个数、是否能表示某个数等信息。

【模板】线性基

给定一个整数数组 $a$ ，构建其线性基。求线性基的最大异或和。

C++

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct linear_basis {
  int64_t bit;            // 线性基的位数
  vector<int64_t> basis;  // 线性基

  bool has_zero = false;  // 原数组是否能表示 0

  explicit linear_basis(int64_t bit = 64) : bit(bit), basis(bit) {}

  // 插入 x 到线性基, 如果插入成功返回 true, 否则返回 false
  // 插入失败表示 x 可以由线性基表示, 即 x 被消为 0, 原数组可以表示 0
  bool insert(int64_t x) {
    for (int64_t i = bit - 1; i >= 0; --i) {
      // x 的第 i 位为 0，跳过
      if ((x >> i & 1) == 0) { continue; }
      if (basis[i] == 0) {  // basis[i] 为空，插入
        basis[i] = x;
        return true;
      }
      x ^= basis[i];  // 消去 x 的第 i 位
    }
    has_zero = true;  // x 被消为 0, 原数组能表示 0
    return false;     // x 被消为 0, 未插入
  };

  // 求线性基中的最大异或和
  int64_t max_xor() const {
    int64_t res = 0;
    for (int64_t i = bit - 1; i >= 0; --i) { res = max(res, res ^ basis[i]); }
    return res;
  };

  // 求线性基中的最小异或和
  int64_t min_xor() const {
    for (int64_t i = 0; i < bit; ++i) {
      if (basis[i] != 0) { return basis[i]; }  // 最小非零异或和
    }
    return 0LL;  // 线性基为空, 最小异或和为 0
  };

  // 求线性基的秩
  int64_t rank() const {
    int64_t res = 0;
    for (int64_t i = 0; i < bit; ++i) { res += static_cast<int64_t>(basis[i] != 0); }
    return res;
  };

  // 求线性基能表示的数的个数: 2^rank
  int64_t size() const { return 1LL << rank(); };

  // 检查 x 是否可以由线性基表示
  bool check(int64_t x) const {
    for (int64_t i = bit - 1; i >= 0; --i) {
      if ((x >> i & 1) == 0) { continue; }
      if (basis[i] == 0) { return false; }  // basis[i] 为空，无法表示
      x ^= basis[i];                        // 消去 x 的第 i 位
    }
    return true;  // x 被消为 0，可以表示
  };
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  linear_basis lb(64);
  for (int64_t i = 0; i < n; ++i) {
    int64_t x;
    cin >> x;
    lb.insert(x);
  }
  cout << lb.max_xor() << "\n";
  return 0;
}

高斯消元⚓︎

高斯消元法通过将向量组表示为矩阵，并对矩阵进行行变换来构建线性基。
该方法可以求出线性基的最大异或和、最小异或和、第 $k$ 大异或和（普通消元法不能求出）、秩、能表示的数的个数、是否能表示某个数等信息。

k 大异或和

给定一个整数数组 $a$ ，构建其线性基。对于 $m$ 个查询，每个查询给出一个整数 $k$ ，求第 $k$ 大异或和。如果 $k$ 超出范围，输出 $-1$ 。

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct guassian_basis {
  vector<int64_t> basis;  // 线性基

  bool has_zero = false;  // 是否能表示 0

  explicit guassian_basis(const vector<int64_t> &nums, int64_t bit = 64) : basis(nums) {
    int64_t n   = nums.size();
    int64_t len = 0;  // 线性基的长度
    // 高斯消元构建线性基
    for (int64_t i = bit - 1; i >= 0; --i) {
      for (int64_t j = len; j < n; ++j) {
        if ((basis[j] >> i & 1) != 0) {  // 找到第 i 位为 1 的数
          swap(basis[j], basis[len]);    // 将其放到前面
          break;
        }
      }
      if ((basis[len] >> i & 1) == 0) { continue; }  // 没有找到，跳过
      for (int64_t j = 0; j < n; ++j) {
        // 消去第 i 位
        if (j != len && (basis[j] >> i & 1) != 0) { basis[j] ^= basis[len]; }
      }
      len++;  // 增加线性基的长度
    }

    basis.resize(len);
    has_zero = len < n;
  }

  // 求k大异或和
  int64_t kth_xor(int64_t k) const {
    if (has_zero && k == 1) { return 0LL; }
    if (has_zero) { k--; }                            // 能表示 0，k 减 1
    if (k >= (1LL << basis.size())) { return -1LL; }  // 超出范围
    int64_t res = 0;
    for (int64_t i = basis.size() - 1, j = 0; i >= 0; --i, ++j) {
      if ((k >> j & 1) != 0) { res ^= basis[i]; }  // 第 i 位为 1，加入 basis[i]
    }
    return res;
  }

  // 求线性基中的最大异或和等信息和普通消元法类似
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int64_t> nums(n);
  for (int64_t i = 0; i < n; ++i) { cin >> nums[i]; }
  guassian_basis gb(nums);

  int m;
  cin >> m;
  for (int64_t i = 0; i < m; ++i) {
    int64_t k;
    cin >> k;
    cout << gb.kth_xor(k) << "\n";
  }
}

向量线性基⚓︎

向量线性基是线性基的一种扩展，适用于处理高维向量空间中的线性无关向量集合。

装备购买

有 $n$ 件装备，每件装备有 $m$ 个属性，装备 $i$ 的属性为 $a_{i1}, a_{i2}, \ldots, a_{im}$ ，且有一个购买费用 $c_i$ 。现在需要从中选择一些装备，使得这些装备的属性向量线性无关，且购买费用之和最小。输出最多能选择多少件装备，以及对应的最小费用。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct linear_basis_vector {
  int64_t m;              // 向量的维度
  vector<int64_t> basis;  // 线性基

  // m: 维度
  explicit linear_basis_vector(int64_t m) : m(m), basis(m, -1) {}

  // 插入向量 v 到线性基
  bool insert(int64_t i, vector<vector<double>> &vectors) {
    const double eps = 1e-5;
    for (int64_t j = 0; j < m; ++j) {
      if (abs(vectors[i][j]) < eps) { continue; }  // x 的第 j 位为 0，跳过
      if (basis[j] == -1) {                        // basis[j] 为空，插入
        basis[j] = i;
        return true;
      }
      // 消去 x 的第 i 位
      double ratio = vectors[i][j] / vectors[basis[j]][j];
      for (int64_t k = j; k < m; ++k) { vectors[i][k] -= ratio * vectors[basis[j]][k]; }
    }
    return false;  // x 被消为 0，未插入
  };
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<vector<double>> vectors(n, vector<double>(m));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) { cin >> vectors[i][j]; }
  }
  vector<int64_t> cost(n);
  for (int i = 0; i < n; ++i) { cin >> cost[i]; }
  vector<int> indices(n);
  iota(indices.begin(), indices.end(), 0);
  // 按照 cost 升序排序, cost 小的优先插入线性基
  sort(indices.begin(), indices.end(), [&](int a, int b) { return cost[a] < cost[b]; });

  linear_basis_vector lb(m);
  int64_t num = 0, total_cost = 0;
  for (int i = 0; i < n; ++i) {
    if (lb.insert(indices[i], vectors)) {
      num++;
      total_cost += cost[indices[i]];
    }
  }
  cout << num << " " << total_cost << "\n";

  return 0;
}

树上线性基⚓︎

树上线性基是线性基的一种应用，适用于处理树结构中的路径查询问题，可以结合 $LCA$ 将路径查询转化为节点的异或和。
每个节点维护从根节点到该节点的线性基。具体来说，孩子节点首先继承父节点的线性基，然后将当前节点的值插入到线性基中。

如果当前节点的值可以由线性基表示，则保留深度较大的值作为线性基的一部分
然后将淘汰的值重新插入到线性基中（根据深度判断是执行异或还是继续淘汰）
直到淘汰的值无法再插入为止

线性基⚓︎

普通消元⚓︎

高斯消元⚓︎

向量线性基⚓︎

树上线性基⚓︎

评论