线性基求交
引理:有两个线性基 , 设 中能被 表示的集合为 ,且 线性无关,则 为 所表示张成的空间的交的一组基。
证明:显然 里的每一个元素都既能被 也能被 表示,而如果一个既能被 ,也能被 表示的元素 无法被 表示,设它在被 表示时用到 内的元素为 , 内的元素为 ,(), 为 的子集,能被 表示, 能被 表示,于是 能被 表示,与假设矛盾。
于是我们只需要将任意一组 转为符合上述条件的一组基。
我们维护一个初始为 A 的线性基(实际上是 ),我们依次枚举每一个 ,判断它能否被这个线性基所表示,如果不能,将它插入,这代表这个元素最后属于 ,如果能,设表示它所用的 中的元素集合为 , 中的元素集合为 ,将 加入 中。
实际上我们就是将加入 的 变为 ,没有加入 的 保证不变。
首先这样 张成的空间一定不变,因为表示每一个改变了的 的 所用的元素都未加入 ,仍在基中(即新的基仍能表示出 ,旧的基本来就是表示出 )。
容易发现这样做我们加入 的元素一定能被 表示,没有加入 的元素一定不能被 表示(因为它没法被一个完全包含 的线性基表示),而我们每次往 加入元素都保证了它无法被现有的 所表示,于是最后得到的 一定合法。
实现上就是在线性基每一位记录一个 f[i]
表示这一位来自 还是 ,插入 的一个元素时直接记录所有它异或上的,为 内的元素的异或和,如果插入失败的话更新 即可(其实如果我们从小往大插入,插入 失败的话 的最高位和 的最高位一定相同。因为我们没有插入任何一个最高位大于等于 的 ,于是可以直接在 上改代表 )