线性基求交

引理：有两个线性基 $A,B$ , 设 $B$ 中能被 $A$ 表示的集合为 $W$，且 $(B\setminus W)\cup A$ 线性无关，则 $W$ 为 $A,B$ 所表示张成的空间的交的一组基。

证明：显然 $W$ 里的每一个元素都既能被 $A$ 也能被 $B$ 表示，而如果一个既能被 $A$，也能被 $B$ 表示的元素 $v$ 无法被 $W$ 表示，设它在被 $B$ 表示时用到 $W$ 内的元素为 $S$，$B \setminus W$ 内的元素为 $T$,($T \neq \emptyset$)，$S$ 为 $W$ 的子集，能被 $A$ 表示，$S \cup T$ 能被 $A$ 表示，于是 $T$ 能被 $A$ 表示，与假设矛盾。

于是我们只需要将任意一组 $B$ 转为符合上述条件的一组基。

我们维护一个初始为 A 的线性基（实际上是 $(B\setminus W)\cup A$ ），我们依次枚举每一个 $B_i$，判断它能否被这个线性基所表示，如果不能，将它插入，这代表这个元素最后属于 $B\setminus W$，如果能，设表示它所用的 $A$ 中的元素集合为 $S_i$，$B$ 中的元素集合为 $T_i$，将 $S_i$ 加入 $W$ 中。

实际上我们就是将加入 $W$ 的 $B_i$ 变为 $S_i$，没有加入 $W$ 的 $B_i$ 保证不变。

首先这样 $B$ 张成的空间一定不变，因为表示每一个改变了的 $B_i$ 的 $T_i$ 所用的元素都未加入 $W$，仍在基中（即新的基仍能表示出 $B_i$，旧的基本来就是表示出 $S_i$）。

容易发现这样做我们加入 $W$ 的元素一定能被 $A$ 表示，没有加入 $W$ 的元素一定不能被 $A$ 表示（因为它没法被一个完全包含 $A$ 的线性基表示），而我们每次往 $B\setminus W$ 加入元素都保证了它无法被现有的 $(B\setminus W)\cup A$ 所表示，于是最后得到的 $W$ 一定合法。

实现上就是在线性基每一位记录一个 f[i] 表示这一位来自 $A$ 还是 $B$，插入 $B$ 的一个元素时直接记录所有它异或上的，为 $A$ 内的元素的异或和，如果插入失败的话更新 $W$ 即可（其实如果我们从小往大插入，插入 $B_i$ 失败的话 $S_i$ 的最高位和 $B_i$ 的最高位一定相同。因为我们没有插入任何一个最高位大于等于 $B_i$ 的 $B_j$，于是可以直接在 $B$ 上改代表 $W$）