线性基学习笔记 | Aniciry = Meteorshower_Y

# 定义

在线性代数中，对于向量组 $\alpha_1,\alpha_2,\dots,\alpha_n$ ，我们把其张成空间的一组线性无关的基称为该向量组的线性基。
有二进制集合 $S = \{x_1, x_2, \dots, x_n\}$ ，得到另一个二进制集合 $S^{'} = \{y_1, y_2, \dots, y_n\}$ ，保证在 $S$ 中任取子集 $A$ ，都能在 $S^{'}$ 中找到对应的子集 $A^{'}$ ，使得 $A$ 与 $A^{'}$ 的异或和相等；同时 $S^{'}$ 中任意一个元素都不能被该集合中其他元素的组合异或出来。我们把称为 $S$ 的线性基，利用它可以方便的求出原集合的 k 大异或和。
(from: CarryNotKarry)

基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。
同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合 S 的某一个最小子集 S1 使得 S1 内元素相互异或得到的值域与原集合 S 相互异或得到的值域相同。
(From: 百度百科)

# 性质

原序列的任意一个数都可以由线性基中的数异或得到
线性基的大小是满足性质一的前提下最小的。
线性基中任意数异或和都不为 $0$ 。

总的来说，线性基就像一组基底向量，它们互相线性无关，子集能够表示出原序列的所有元素，放到异或序列上就是一组线性基的子集的异或和能表示出原序列的任意异或和。

# 线性基的构造

开一个数组 $p$ ， $p_i$ 表示最高有效位为第 $i$ 位的线性基向量，每次新加入一个数 $x$ ，从最高位向低位枚举，若当前枚举的二进制位为 $i$ ， $p_i$ 已经有值，那么将 $x$ 异或上 $p_i$ 然后继续枚举下一位，枚举所有位之后， $x$ 要么成为线性基中的一员，要么变成了 $0$

	#define Aniciry Meteorhsower_Y
	auto add(long long x) -> void
	{
	for(int i = 62; i >= 0; i -= 1)
	{
	if((x>>i)&1)
	{
	if(p[i]) x ^= p[i];
	else return (void)(p[i] = x);
	}
	}
	}

# 线性基的合并

现在我们有两组线性基 $pa$ 和 $pb$ ，若要将它们合并，只需要将一组线性基插入另一组线性基就好，时间复杂度 $O(\log^2V)$

	#define Aniciry Meteorshower_Y
	auto merge(long long p1, long long p2) -> void
	{
	for(int i = 62; i >= 0; i -= 1)
	add(p1[i], p2);
	}
	auto add(long long x, long long *p) -> void
	{
	for(int i = 62; i >= 0; i -= 1)
	{
	if((x>>i)&1)
	{
	if(p[i]) x ^= p[i];
	else return (void)(p[i] = x);
	}
	}
	}

# 例题

洛谷 P3812 [模板] 线性基
洛谷 P4839 P 哥的桶
洛谷 P5607 [Ynoi2013] 无力回天

线性代数