线性基学习笔记 / 洛谷 P3812 【线性基】【贪心】

线性基学习笔记

前置芝士：

假设有 $\overrightarrow{a_1}$，$\overrightarrow{a_2}$，$\cdots$，$\overrightarrow{a_n}$ 等 $n$ 个向量所构成的向量组。

然后定义一个常数组 $c_1$，$c_2$，$c_3$，$\cdots$，$c_n$，让他们两两相乘，得到一个子空间 $c_1\overrightarrow{a_1}$，$c_2\overrightarrow{a_2}$，$c_3\overrightarrow{a_3}$，$\cdots$，$c_n\overrightarrow{a_n}$。其中 $a_n\in \text{N}$。

假设一个向量组 $a_1,a_2,a_3,\cdots ,a_n$ 和另外的一个向量组 $b_1,b_2,b_3,\cdots ,b_n$ 可以用上面的方法互相转换，那么他们是等价的。

---

给定一个向量组 $a_1,a_2,a_3,\cdots ,a_n$，现在要求求出一组他们的基。

需要使用高斯等消元法来求解。

当使用高斯消元消完某一列的时候，会形成一个三角形，类似于 ┕图 $1$┑，这个三角一定是线性无关的。原因，这里面的任意一个向量无法被其他向量表示。

容易发现时间复杂度为 $O(n^3)$。

---

对于任意的一组向量 { x ⃗ 1 , x ⃗ 2 . x ⃗ 3 , ⋯   , x ⃗ n } \{\vec x_1,\vec x_2.\vec x_3,\cdots,\vec x_n\} {x 1​,x 2​.x 3​,⋯,x n​}，他都可以用上面所述的方法生成一个东西叫做子空间，这个子空间里面的任意基底都是等价的。

重要：假设有一个向量组 { x ⃗ 1 , x ⃗ 2 , x ⃗ 3 ⋯ x ⃗ n } \{\vec x_1,\vec x_2,\vec x_3\cdots\vec x_n\} {x 1​,x 2​,x 3​⋯x n​}，其最大线性无关组的大小一定是小于等于他的维度的。假设维度为 $63$，那么 $63$ 个向量构成的向量组可以代替这 $n$ 个向量组。线性基的重中之重

大量优化需要使用的时间。

---

例题 洛谷 P3812

给定 $n$ 个整数，求在这些数中选取多少个数让异或和最大。$1\le n\le 50$，$0\le a_i\le 2^{50}$。

实际上就是求最大的生成子空间。

暴力时间复杂度 $O(2^n)$，明显超时。

首先找到 $n$ 个向量的线性基，大约有 $50$ 个有用的。

然后进行贪心，将所有的向量的线性基进行异或就是答案。

#include 
#define int long long

using namespace std;

int a[100];

signed main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i ++)
    cin >> a[i];
  int k = 0;
  for (int i = 50; i >= 0; i --) {
    for (int j = k; j < n; j ++)
      if (a[j] >> i & 1) {
        swap (a[j], a[k]);
        break;
      }
    if (a[k] >> i & 1) {
      for (int j = 0; j < n; j ++)
        if (j != k)
          if (a[j] >> i & 1)
            a[j] ^= a[k];
      k ++;
      if (k >= n)
        break;
    }
  }
  int res = 0;
  for (int i = 0; i < k; i ++)
    res ^= a[i];
  cout << res << '\n';
  return 0;
}

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

AC Record

---

图

图 $1$：

其中黑色框好的为非 $0$ 数，其他的 $0$。