线性基和高斯消元有时会联系在一起。
概念
线性基，大多数时候的应用是 \(O(\log V)\) 求异或和最大子集，但是本质上是高维向量空间中的一组基。
一般线性基
一般的二进制线性基是容易构造的，只需要检查每个数是否可以作为基底。
插入复杂度 \(O(\log V)\)，查询复杂度 \(O(\log v)\)，不支持修改。
void update(ll x)
{
for (int i = 61; i >= 0; i--)
{
if (x & (1ll << i))
{
if (!b[i])
{
b[i] = x;
return;
}
else x ^= b[i];
}
}
}
ll query()
{
ll res = 0;
for (int i = 61; i >= 0; i--)
if ((res ^ b[i]) > res) res ^= b[i];
return res;
}
合并
支持单向合并，不支持分裂，单次复杂度 \(O(\log^2 V)\).
只需要考虑将其中一个线性基的全部基底插入另外一个线性基即可。
basis merge(basis a, basis b)
{
basis res = a;
for (int i = lg_sz - 1; i >= 0; i--) res.insert(b.b[i]);
return res;
}
前缀线性基
经典的应用是求解一段区间构成的线性基。
-
解一：使用线段树大力合并
-
预处理复杂度 \(O(4n \log^2 n)\).
-
修改复杂度 \(O(\log^3 n)\).
-
查询复杂度 \(O(\log^3 n)\).
-
-
解二：使用 RMQ 大力合并
-
预处理复杂度 \(O(n \log^3 n)\).
-
查询复杂度 \(O(\log^2 n)\).
-
不支持修改.
-
-
解三：前缀线性基。
考虑对于原序列的每一段前缀，维护一个前缀线性基。
对于每个二进制位，维护可以贡献它的基底中下标最大的一个。
插入的时候如果存在基底，考虑将插入的数和基底中下标较小的一个继续向下插入，另一个作为当前位的基底。
查询只需要第 \(r\) 个前缀线性基中下标大于等于 \(l\) 的基底。
-
预处理复杂度 \(O(n \log n)\).
-
查询复杂度 \(O(\log n)\).
-
不支持修改。
-
-
解四：用猫树分治维护区间线性基。
关于一种快速离线区间线性基，参考 关于一种快速离线区间线性基 - zhiyangfan 的小窝
一类贪心问题
给定若干向量（元素），选择每个元素有相应的代价，试求原向量集中代价最小的一组线性无关基底。
考虑贪心从小到大插入线性基，得到的就是最小基底。
求代价最大的基底就降序排序。
线代意义
一般的线性基可以看作是特定情况下的。
线性基的真正意义是维护向量空间中一组线性无关的基底，所以对于高维的向量集可以考虑用高斯消元求出此时的一组线性基。
根据基底的定义，在向量空间，一组 \(n\) 个线性无关的 \(n\) 维向量构成一组基。
所以我们只需要考虑在插入的时候判定线性无关，反之直接令其作为基底。
假设现在的向量集是 \(A, |A| = n\).
考虑一直插入到第 \(i - 1\) 个向量，尝试插入第 \(i\) 个向量。
如果第 \(i\) 个向量和之前的 \(i - 1\) 个向量线性有关，则根据定义可以设：
\[k_1 A_{1, 1} + k_2 A_{2, 1} + \cdots + k_n A_{i - 1, 1} = A_{i, 1} \\ \cdots \\ k_1 A_{1, n} + k_2 A_{2, n} + \cdots + k_n A_{i - 1, n} = A_{i, n} \]本质上就是一个线性方程组，考虑用高斯消元求解就行。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef double db;
const int maxn = 505;
const int maxm = 505;
const db eps = 1e-4;
struct item
{
int cost;
db x[maxm];
bool operator < (const item& rhs) const { return (cost < rhs.cost); }
} a[maxn];
int n, m;
int b[maxm];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%lf", &a[i].x[j]);
for (int i = 1; i <= n; i++) scanf("%d", &a[i].cost);
sort(a + 1, a + n + 1);
int cnt = 0, sum = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (fabs(a[i].x[j]) > eps)
{
if (!b[j]) { cnt++, sum += a[i].cost, b[j] = i; break; }
db lf = a[i].x[j] / a[b[j]].x[j];
for (int k = j; k <= m; k++) a[i].x[k] -= a[b[j]].x[k] * lf;
}
}
}
printf("%d %d\n", cnt, sum);
return 0;
}