笔记 - 异或线性基

发表于 更新于 分类于 ， 本文字数： 969 阅读时长 ≈ 4 分钟

令 \(V\subseteq\mathbb{Z}_2^n\), 异或线性基即为线性空间 \(V\) 上满足一定条件的一组 Hamel 基 \((\epsilon_0,\epsilon_1,\dots,\epsilon_n)\)

线性基

定义

令 \(V\subseteq\mathbb{Z}_2^n\), 线性基即为线性空间 \(V\) 上满足如下条件的一组 "基底" \((\epsilon_0,\epsilon_1,\dots,\epsilon_n)\)

  1. 排除 \(\epsilon_0,\epsilon_1,\dots,\epsilon_n\) 中所有零向量后的向量组线性无关
  2. \(\epsilon_i(i+1..n)=0\)
  3. 若 \(\epsilon_i(i)=1\), 则 \(\forall j,~\epsilon_j(i)=\delta_{ij}\)

对 \(\alpha\in\mathbb{P}^n\), \(\alpha(x)\) 即为 \(\alpha\) 第 \(x\) 维的元素，\(\alpha(x..y)\) 即为 \(\alpha\) 第 \(x\) 维到第 \(y\) 维所有元素构成的向量

写成矩阵来看更直白些，矩阵看起来就像是缺了几列的三角形

比如这样

\[ (\epsilon_0,\epsilon_1,\dots,\epsilon_6)=\begin{bmatrix} & & & & &1\\ & & & &1& \\ & & &0&1&1\\ & &1& & & \\ &1& & & & \\ 1& & & & & \\ \end{bmatrix} \]

性质

  • \(\operatorname{span}(\epsilon_0,\epsilon_1,\dots,\epsilon_n)=\operatorname{span}(V)\)

  • 令 \(\alpha[x]=\sum_{i=1}^n\alpha(i)x^{i-1}\), 则

    \[ \left[\sum_{i=1}^n\epsilon_i\right](2)=\max_{\alpha\in\operatorname{span}(V)}\alpha[2] \]

    在后面的代码实现中可以看到，这条性质说的是将所有线性基异或起来的值即为 \(V\) 的最大子集异或和

构造方法

我们以插入元素的方法构造

对前设的 \(V\), 设当前我们已完成构建的线性空间为 \(V'\subseteq V\), 对应的线性基为 \((\epsilon'_0,\epsilon'_1,\dots,\epsilon'_n)\), 接下来我们在 \(V\setminus V'\) 中选取一个向量 \(\alpha\), 进行如下操作直到 \(|V'|=|V|\) 为止

\(\begin{array}{r|l:l} 1 & \textbf{for}~ i \gets n ~\textbf{downto}~ 1 ~\textbf{do} \\ 2 & \quad \textbf{if}~ \alpha(i) = 1 ~\textbf{then}\\ 3 & \quad \quad \textbf{if}~ \epsilon'_i(i) = 1 ~\textbf{then}~ \alpha\gets\alpha+\epsilon'_i & flip~\alpha(i)\\ 4 & \quad \quad \textbf{else} & prepare~to~replace~\epsilon'_i~with~\alpha\\ 5 & \quad \quad \quad \textbf{for}~ j \gets 0 ~\textbf{to}~ i-1 ~\textbf{do} \\ 6 & \quad \quad \quad \quad \textbf{if}~ \alpha(j) = 1 ~\textbf{then}~ \alpha\gets\alpha+\epsilon'_j & flip~\alpha(j)\\ 7 & \quad \quad \quad \textbf{end}~\textbf{for} \\ 8 & \quad \quad \quad \textbf{for}~ j \gets i+1 ~\textbf{to}~ n ~\textbf{do} \\ 9 & \quad \quad \quad \quad \textbf{if}~ \epsilon'_j(i) = 1 ~\textbf{then}~ \epsilon'_j\gets\alpha+\epsilon'_j & flip~\epsilon'_j(i)\\ 10 & \quad \quad \quad \textbf{end}~\textbf{for} \\ 11 & \quad \quad \quad \epsilon'_i\gets\alpha & replace\\ 12 & \quad \quad \quad \textbf{goto}~ line~ 16 \\ 13 & \quad \quad \textbf{end}~\textbf{if} \\ 14 & \quad \textbf{end}~\textbf{if} \\ 15 & \textbf{end}~\textbf{for} \\ 16 & restore~\alpha~and~insert~\alpha~to~V',~delete~\alpha~from~V \end{array}\)

正确性

可用归纳法证明

  • \(V'=\varnothing\) 与 \(|V'|=1\) 时显然满足条件
  • 当 \(|V'|>1\) 时
    • 我们尝试插入 \(\alpha\) 时，如果满足第 \(3\) 行的条件，为了保持条件 \(2\), 我们需要把对应维反转，如果 \(\alpha\) 被转成 \(0\) 了，说明 \(\alpha\) 与 \((\epsilon'_0,\epsilon'_1,\dots,\epsilon'_n)\) 线性相关，不能插入
    • 如果执行到第 \(4\) 行，说明 \(\alpha\) 与 \((\epsilon'_0,\epsilon'_1,\dots,\epsilon'_n)\) 线性无关，此时应做一些处理来维持线性基的条件，之后替换掉 \(\epsilon'_i\) 即可 (此时的 \(\epsilon'_i=0\))
      • \(5\sim 7\) 行是消除 \(\alpha\) 中低维的不满足条件 \(3\) 的 \(1\)
      • \(8\sim 10\) 行是消除 \(\epsilon'_j\) 中第 \(i\) 维的 \(1\), 同样是为了满足条件 \(3\)
    • 经过这样的处理之后，插入 \(\alpha\) 后的 "基底" 仍满足条件 \(3\)

复杂度

令 \(n\) 为维数

  • 时间复杂度:
    • 插入: \(O(n)\)
  • 空间复杂度: \(O(n)\)

代码

众所周知，\(\mathbb{Z}_2\) 上的加法即为异或，故代码实现时可以将 \(V\) 中元素写为无符号整形或 std::bitset, 加法即为异或

Show code

Xor_base.hppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
template <std::size_t N = 64>
class XorBasis {
  using self = XorBasis<N>;
  using field_t = bool;
  using vector_t = std::bitset<N>;
  using reference = self &;
  using iterator = vector_t *;
  using const_iterator = vector_t *;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

protected:
  vector_t base[N];

public:
  constexpr XorBasis() { this->clear(); }
  constexpr XorBasis(std::initializer_list<vector_t> _list): XorBasis() {
    for (auto &&i : _list) this->insert(i);
  }

  constexpr void clear() {
    for (size_t i = 0; i < size(); ++i) base[i].reset();
  }

  constexpr size_t size() const { return N; }

  constexpr vector_t &operator[](size_t index) { return this->base[index]; }
  constexpr vector_t &operator[](size_t index) const {
    return const_cast<self * const>(this)->base[index];
  }

  constexpr iterator begin() { return this->base; }
  constexpr const_iterator begin() const {
    return const_cast<vector_t * const>(this->base);
  }

  constexpr iterator end() { return this->begin() + this->size(); }
  constexpr const_iterator end() const { return this->begin() + this->size(); }

  reverse_iterator rbegin() { return reverse_iterator(this->end()); }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(this->end());
  }

  reverse_iterator rend() { return reverse_iterator(this->begin()); }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(this->begin());
  }

  constexpr bool insert(vector_t x) {
    bool status = false;
    for (size_t i = size() - 1; ~i; --i) {
      if (!(x[i])) continue;
      if (base[i][i]) x ^= base[i];
      else {
        for (size_t j = 0; j < i; ++j)
          if (x[j]) x ^= base[j];
        for (size_t j = i + 1; j < size(); ++j)
          if (base[j][i]) base[j] ^= x;
        base[i] = x;
        status = true;
        break;
      }
    }
    return status;
  }

  constexpr vector_t max_span() const {
    vector_t ret;
    for (const auto &i : *this) ret ^= i;
    return ret;
  }

  constexpr size_t rank() const {
    size_t res = 0;
    for (size_t i = 0; i < size(); ++i) res += base[i][i];
    return res;
  }

  // @return std::nullopt if x is linear independent with current basis, else
  // return the solution
  constexpr std::optional<vector_t> coordinate(vector_t x) {
    vector_t res;
    for (size_t i = size() - 1; ~i; --i) {
      if (x[i] && !base[i][i]) return std::nullopt;
      if (x[i] && base[i][i]) {
        res.set(i);
        x ^= base[i];
      }
    }
    return res;
  }
};

例题