线性基的交

题解

线性基的交：假设有$A,B$两个线性基，要求出一个线性基$C$，使得$C$表示的线性空间为$A$所表示的线性空间和$B$所表示的线性空间的交。$C$即为线性基$A,B$的交。

下面先说线性基怎么求交。如果我们有$A,B$两个线性基，要求它们的交线性基$C$，那么显然$B$中所有能被A线性基表示的数，都要插入$C$中，之后如果 $A 并 ( B ∖ C )$ 线性无关（$B ∖ C$ 代表$B$中所有不能被$A$线性基表示的数），则$C$就是$A,B$的交线性基。（证明：若 $V1,V2$ 分别是 $A,B$ 构成的线性空间，令 $W = B 交 V1$ ，则需要证明的为：若 $A 并 (B ∖ W)$ 线性无关，则 $W$ 是 $V1 交 V2$ 的一组基。考虑任意 $v ∈ V1 交 V2$，那么$v$可以同时被$A$和$B$表出。考虑如何证明$v$可以被$W$线性表示。我们假设$v$不能可以被$W$线性表示，那么$v$一定可以被$S$和$T$共同线性表示，其中$S ∈ W,T ∈ B ∖ W$，且其中$T$不为空。那么此时$T$一定与$A$线性相关（因为向量组$S并T$和$A$均与$V1 交 V2$等价，所以$S并T$与$A$等价，所以$A$可以表示出$T$），与我们的前提不符。所以上述假设成立）

但问题是 $A 并 ( B ∖ C )$ 未必线性无关，所以我们采取下面这种做法。再额外创建一个线性基$D$，同时$D$上每一位再额外保存一个值$v$，一开始把$A$中所有的数字 $A[i]$ 插入$D$，并把对应插入位置的$v$也改为 $A[i]$。之后从低位到高位，将$B$中每一个数字 $B[i]$ 插入$D$，每次插入时，维护一个$u$值，$u$一开始等于$1$，插入时每访问到$D$的某一位，$u$就等于$u$异或对应位上的$v$。

如果 $B[i]$ 可以被$D$表示，那么插入一定失败，把 $u$ 插入$C$；如果 $B[i]$ 不可以被$D$表示，那么一定会将一个值$X$插入$D$中某一位，同时把对应位的$v$值改为$u$。这样将$B$遍历完毕之后，$C$就是$A$和$B$的交线性基。

时间复杂度为$log(b^2)$，其中$b$为线性基的维数。

线性基的并：假设有$A,B$两个线性基，要求出一个线性基$C$，使得$C$表示的线性空间为$A$所表示的线性空间和$B$所表示的线性空间的并。$C$即为线性基$A,B$的并。（有题解说可以用容斥原理结合求交实现，但并真的可能存在么？比如说线性基$A$中只有$10$，$B$中只有$01$，那么显然$C$表示的线性空间应该为${10,01}$，但是显然不存在$C$满足此条件，因为若$01,10$都在线性空间中，那么$01+10=11$必然在线性空间中）