线性基#

概述#

通常可以解决有关异或的一些题目。

对于给定的数集 $A$ ，线性基是一个子集 $P\subset A$ ，其满足：

原序列里面的任意一个数，都可以由线性基里面的若干个数按位异或得到；
任意若干个数，异或和不为 $0$ .
是满足上述条件的最小子集。

能求出：给定集合的最大异或和。

构造#

//插入一个long long范围内的整数
int p[65];
void insert(int x) {
    for(int i = 62; i >= 0; i--) {
        if(x & (1ll << i)) {
            if(!p[i]) { p[i] = x; break; }
            x ^= p[i];
        }
    }
}

cpp

在二进制下， $p[i]$ 代表线性基中，最高位是第 $i$ 位的元素。

显然每个数位最多需要一个元素，因为当 $p_i=2^i$ 时，所有数都能被线性基表出。

上面这段代码中，用 $x_i$ 表示 x 在运行过程中的取值，那么其含义为：要让 $x$ 能被线性基表出，则只需 $x_i$ 可以被线性基表出。

循环第一次进行时，我们需要 $x$ 能被表出，用 $i$ 表示二进制下 $x$ 的最高位，则：

若 $p_i$ 为空， $p_i\leftarrow x$ ，直接填入后跳出循环。
若 $p_i$ 非空，由于 $p_i$ 已经可以被表出了，要想让 $x$ 能被表出，就只需要 $x\oplus p_i$ 可以被表出。所以让 $x\leftarrow x\oplus p_i$ ，注意到 $p_i\oplus x$ 的最高位会变小，会在后面的循环中被处理，这很合理。

若当循环结束时， $p_i\leftarrow x$ 还没有被执行过，说明 $x$ 在插入前就可以被线性基表出了。

查询异或最值#

还没写完

前缀线性基#

考虑线性基的插入过程，线性基上每一位的数，都是对应位上在原数列最左侧的数字。现在我们进行改变，使得线性基上每一位的数，都变成对应位上在原数列最右侧的数字。

代码实现：

struct Linear_Basis{
	int p[24], pos[24];
	void insert(int x, int id) {
		for(int i = 23; i >= 0; i--) {
			if(x & (1ll << i)) {
				if(!p[i]) { p[i] = x, pos[i] = id; break; }
				else if(id > pos[i]) { swap(pos[i], id), swap(x, p[i]); }
				x ^= p[i];
			}
		}
	}
	int qry_max(int l) {
		int ret = 0;
		for(int i = 23; i >= 0; i--)
			if(pos[i] >= l && (ret ^ p[i]) > ret) ret ^= p[i];
		return ret;
	}
} lb;

cpp

尽可能用右侧的数来作为基，所以要用 $x$ 替换掉 $p_i$ 的位置。

插入之后需要 $\mathrm{swap}(x, p_i)$ ，因为此时的线性基已经能表出 $x$ 了，但原先的 $p_i$ 不能被表示了。

直接取出所有 $pos_i\geq l$ 的 $p_i$ ，就是 $a_{[l,r]}$ 的线性基。

原因：还是要看上面插入函数流程的含义。若一个 $p_i$ 所对应的 $pos_i<l$ ，说明在插入 $a_{[l,r]}$ 这些数时， $p_i$ 是否存在于 $a_{[l,r]}$ 能否被表出是无关的。因此 $pos_i<l$ 的 $p_i$ 不在 $a_{[l,r]}$ 的线性基中。