「Note」2022-06-23 线性基

How interesting

$\mathbb{Definition}$

现有一正整数集 $S$ ，关于 $S$ 构造的线性基可以视为另一个集合，且满足以下性质

• 可以通过线性基中子集的异或值得到 $S$ 中所有子集的异或值，且线性基的元素个数在满足条件的情况下最小
• 线性基中子集异或值不存在 $0$
• 线性基中不同子集的异或值不同
• 线性基中不同元素的二进制最高位互不相同

不严谨的一句话概述：线性基与原集合在关于异或的问题上等价，且元素个数小于原集合。

$\mathbb{Build}$

首先令线性基元素集合为 $Base$ 。

$\mathbb{Insert}$

在插入某个数 $val$ 时，从二进制最高位往最低位扫。

在第 $i$ 位有值的情况下，若 $base_i$ 不存在，就 $base_i := val$，否则 $val \otimes base_i$ 。

insert.cpp

void insert (LL val) {
	for (int i = BIT; i >= 0; i--) {
		if ((1ll << i) & val) {
			if (base[i] == 0) {
				base[i] = val;;
				break;
			} else val ^= base[i];
		}
	}
}

$\mathbb{Min/Max \ Query}$

贪心思想

query_min_max.cpp

LL query_min() {
	for (int i = 0; i <= BIT; i++) if (base[i]) return base[i];
	return 0;
}
LL query_max() {
	LL res = 0;
	for (int i = BIT; i >= 0; i--) if ((res ^ base[i]) > res) res ^= base[i];
	return res;
}

$\mathbb{Kth \ query}$

首先对线性基进行改造，使得线性基的每一位都相互独立。
目标是在改造后使得二进制的每一位 $i$ 上，除了 $base_i$ 是 $1$ 其他的均为 $0$ 。
具体来说，从高往低扫，如果存在 $i < j$ ，且 $a_j$ 的第 $i$ 位是 $1$，就将 $a_j$ 异或上 $a_i$。
查询就是二进制拆分。

query_kth.cpp

void rebuild() {
	for (int i = BIT; i >= 0; i--)
		for (int j = i - 1; j >= 0; j--) if (base[i] & (1ll << j))
			base[i] ^= base[j];
	for (int i = 0; i <= BIT; i++) if (base[i]) p[cnt++] = base[i];
}
int querykth(int k) {
	int res = 0;
	if (k >= (1ll << cnt)) return 0x3f3f3f3f;
	for (int i = BIT; i >= 0; i--) if (k & (1ll << i)) {
		res ^= p[i];
	}
	return res;
}