下文中的「线性基」都是指异或线性基。
我自认为比 GM 给的那篇博客讲的清楚，，，当然是假的。
不过说起来我不是很懂为什么 CSP 之前要学这么偏的知识点。。。
定义
给出一个序列，存在一个由 任意整数 构成的集合，满足原序列中的任意一个数都可以由若干个集合中的数 异或 得到，这个不一定唯一的集合被称为线性基。
性质
-
原序列中的任意一个数都可以由线性基中的若干个数异或得到。
-
线性基中任意若干个数异或起来都不为 \(0\)。
-
在所有满足 \(1,2\) 性质的整数序列中，线性基的大小最小。
-
存在性：任意整数序列均存在至少一个线性基。
明显这个东西我不会证也看不懂，所以我们拉一段 wiki 上的话。
设线性空间 \(V\) 的全体线性无关向量组为 \(\mathscr F\), 显然 \((\mathscr F, \subseteq)\) 构成偏序集。
翻译一下。
设 \(V\) 是原序列，则 \(\mathscr F\) 包含所有满足性质 1 和 2，但不一定满足性质 3 的集合。也就是说 \(\mathscr F\) 是一个集合套集合。
而 \((\mathscr F,\subseteq)\) 是一个偏序集，就是 CDQ 那个偏序，\(\subseteq\) 的意思是，为 \(\mathscr F\) 规定一个附带的条件 \(\subseteq\)，会为一些操作中给出限制，但里面包含的元素与 \(\mathscr F\) 完全一致。
容易验证 \((\mathscr F,\subseteq)\) 上的任意全序子集均有上界，故由 Zorn 引理，\(\mathscr F\)有极大元 \(F\)。
全序集是指，对于任意 \(a,b\in (\mathscr F,\subseteq)\)，若 \(a,b\in F\)，且 \(a\subseteq b\) 和 \(b\subseteq a\) 中至少有一个成立，则称 \((\mathscr F,\subseteq)\) 为全序集。
那么这句话的意思就是，\((\mathscr F,\subseteq)\) 中的任意全序子集 \(B\) 都能找到一个 \(a\in (\mathscr F,\subseteq)\)，满足对于任意 \(x\in B\)，都有 \(x\subseteq a\)。
这个非常的明显，因为对于任意集合 \(S\) 满足性质 1 和 2，我们都可以通过在满足性质 1 和 2 的情况下不断向里面添加元素得到更大的集合 \(S'\)，此时 \(S\subseteq S'\)。
有 Zorn 引理：
在任何一非空的偏序集中，若任何全序的子集都有上界，则此偏序集内必然存在（至少一枚）极大元。
所以这个时候 \(\mathscr F\) 就存在一个极大元 \(F\)。极大元的意思是，无法找到 \(\mathscr F\) 中的其他元素 \(a\)，满足 \(a\subseteq F\)。
注意虽然这里我们管 \(F\) 叫极大元，但因为偏序 \((\mathscr F,\subseteq)\) 的运算符为 \(\subseteq\)，所以 \(F\) 实际上是大小最小的。然后我们知道 \(\mathscr F\) 由所有满足性质 1 和 2，但不一定满足性质 3 的集合构成，所以 \(F\) 就是线性基。
实现
假设原序列为 \(A\)，现在已经得到 \(A_1\sim A_{i-1}\) 的线性基，接下来需要在这个线性基上作出修改，使得其成为 \(A_1\sim A_i\) 的线性基。
一个简单的方法是插入。
inline bool Hamel(int x) {
for (int i = 55; ~i; --i) {
if (x & (1ll << i)) {
if (h[i])
x ^= h[i];
else {
h[i] = x;
return 1;
}
}
}
return 0;
}
接下来我们来验证进行了插入操作的 \(h\) 数组是否为 \(A_1\sim A_i\) 的线性基。
首先我们需要知道：因为插入成功，即 return 1 时，因为大前提是 x & (1ll << i) == true，所以 \(h_i\) 的第 \(i\) 位一定为 \(1\)。
-
原序列中的任意一个数都可以由线性基中的若干个数异或得到
问题可转化为 \(A_i\) 是否可以由 \(h\) 中的若干个数异或得到、
-
当插入操作失败，即执行
return 0时那么这时候，对于任意时刻的 \(x\)，它的首位（第 \(i\) 位），\(h_i\ne 0\)。
上面我们也说了，\(h_i\) 的第 \(i\) 位为 \(1\)，然后它会和 \(x\) 进行异或，此时 \(x\) 的第 \(i\) 位为 \(0\)。
从 \(i=1\) 开始推导，可以发现 \(h\) 数组满足 \(h_i\) 的最高位为第 \(i\) 位。那么 \(x\) 的最高位被清除。
循环结束，\(i\) 枚举了 \(x\) 任意时刻的所有最高位并将其清除，此时 \(x\) 为 \(0\)。
因为 \(x\) 全程只通过与 \(h_i\) 异或改变自身的值，所以可以得到：
\[x\oplus h_{a_1}\oplus h_{a_2}\oplus\cdots\oplus h_{a_k}=0 \]因为我们知道，有且仅有 \(x\oplus x=0\)，所以：
\[h_{a_1}\oplus h_{a_2}\oplus\cdots\oplus h_{a_k}=x \]此时 \(x\) 不需要被插入，原线性基即为 \(A_1\sim A_i\) 线性基。
-
当插入操作成功，执行
return 1时
-
后面写了一堆没保存。抑郁了。摆了。
标签：mathscr,220924,笔记,任意,异或,归档,线性,oplus,subseteq From： https://www.cnblogs.com/XSC062/p/16724950.html