1. 线性代数建模
把整数 $x\in[0,2^m)$ 看作 $\mathbb F_2^m$ 中的向量，异或就是向量加法。
非空集合 $A$ XOR-closed，当且仅当 $A$ 是一个线性子空间，即
$$ A=\operatorname{span}(A). $$
设我们最终选择进行操作的整数集合为 $X$，那么第 $i$ 个集合最终变成
$$ S_i\cup X. $$
要求所有 $S_i\cup X$ 都是线性子空间，并最小化 $|X|$。
2. 维护全局必需子空间 $W$
维护一个线性子空间 $W$，表示我们已经证明“最终每个集合都必须拥有”的元素。
初始令
$$ W=\{0\}. $$
因为任何非空线性子空间都必须包含 $0$。
检查每个集合
$$ A_i=S_i\cup W. $$
如果 $A_i$ 不是线性子空间，则存在
$$ x\in\operatorname{span}(S_i\cup W)\setminus(S_i\cup W). $$
这个 $x$ 在任何合法答案中都必须被操作加入。
证明如下：设某个合法答案的操作集合为 $X$。最终集合 $S_i\cup X$ 是线性子空间，并且包含 $S_i\cup W$，所以必然包含
$$ \operatorname{span}(S_i\cup W). $$
因此它包含 $x$。但 $x\notin S_i$，所以只能有 $x\in X$。一旦操作了 $x$，所有集合都会拥有 $x$。
因此可以安全地更新
$$ W\leftarrow\operatorname{span}(W\cup\{x\}). $$
因为 $x\notin W$，每次更新都会使
$$ \dim W $$
至少增加 $1$。整个空间的维数只有 $m$，所以最多更新 $m$ 次。
3. 如何判断 $S_i\cup W$ 是否闭合
设
$$ r_i=\dim\operatorname{span}(S_i\cup W), $$
则
$$ \left|\operatorname{span}(S_i\cup W)\right|=2^{r_i}. $$
另一方面，
$$ |S_i\cup W| = |S_i|+|W|-|S_i\cap W|. $$
又因为
$$ S_i\cup W\subseteq\operatorname{span}(S_i\cup W), $$
所以
$$ S_i\cup W\text{ XOR-closed} \iff |S_i|+|W|-|S_i\cap W|=2^{r_i}. $$
因此只需要为每个集合维护：
- $r_i=\operatorname{rank}(S_i\cup W)$；
- $t_i=|S_i\cap W|$。
不需要显式构造 $S_i\cup W$。
4. 如何找到缺失的 $x$
如果
$$ |S_i\cup W|<2^{r_i}, $$
就利用 $S_i\cup W$ 的线性基枚举其 span，找到第一个同时满足
$$ x\notin S_i,\qquad x\notin W $$
的元素即可。
看起来 span 可能很大，但只对当前找到的一个不合法集合枚举，并且找到第一个缺失元素就停止。
在找到缺失元素之前，枚举出来的所有元素都属于 $S_i\cup W$，所以一次寻找最多检查
$$ |S_i\cup W|+1 $$
个元素。
5. 如何维护 $W$
保存 $W$ 中的所有元素，并用 inW[x] 判断成员关系。
假设加入了一个满足 $x\notin W$ 的向量，那么
$$ \operatorname{span}(W\cup\{x\}) = W\cup(x\oplus W). $$
也就是说，新增加的元素恰好为
$$ \{x\oplus w\mid w\in W\}. $$
因此每次维数增加 $1$，$W$ 的大小恰好翻倍。
所有更新过程中生成的 $W$ 元素总数至多
$$ 1+2+4+\cdots+2^m=O(2^m). $$
为了维护 $|S_i\cap W|$，对每个整数 $x$ 建立倒排表，记录它原本出现在哪些集合中。当 $x$ 第一次进入 $W$ 时，更新对应集合的交集大小。
6. 维护每个集合的线性基
初始化时为每个 $S_i$ 建立线性基 $B_i$。
每次找到新的独立向量 $x$ 后，将 $x$ 插入所有 $B_i$。这样 $B_i$ 始终表示
$$ \operatorname{span}(S_i\cup W). $$
一次插入线性基的复杂度为 $O(m)$，最多更新 $m$ 次，所以这一部分复杂度为
$$ O(nm^2). $$
7. 最终答案
设
$$ C=\bigcap_i S_i. $$
稳定后，所有 $S_i\cup W$ 都已经是线性子空间。
但 $W$ 中原本就在所有集合里的元素不需要操作，所以输出
$$ X=W\setminus C. $$
对于任意 $i$：
$$ S_i\cup X=S_i\cup W, $$
因此答案合法。
同时，之前的推导证明了 $W$ 中任何不在所有原集合中的元素都必须被操作，所以该答案也是最优的。
8. 正确性证明
引理 1
如果当前 $W$ 是任何合法最终方案都必须共同拥有的子空间，并且
$$ x\in\operatorname{span}(S_i\cup W)\setminus(S_i\cup W), $$
那么任何合法答案都必须选择 $x$。
证明：最终的第 $i$ 个集合是一个包含 $S_i\cup W$ 的线性子空间，因此包含其 span。于是它包含 $x$。又因为 $x\notin S_i$，所以必须通过全局操作加入 $x$。证毕。
引理 2
每次更新都会使 $\dim W$ 增加 $1$。
因为选出的 $x\notin S_i\cup W$，特别地 $x\notin W$。所以
$$ \dim\operatorname{span}(W\cup\{x\}) = \dim W+1. $$
证毕。
引理 3
算法最多更新 $m$ 次。
根据引理 2，每次更新维数增加 $1$，而 $W\subseteq\mathbb F_2^m$，所以 $\dim W\le m$。证毕。
引理 4
算法结束时输出的方案合法。
结束时对所有 $i$ 都有
$$ |S_i\cup W| = 2^{\operatorname{rank}(S_i\cup W)}. $$
由于 $S_i\cup W$ 包含于它的 span，且两者大小相等，因此
$$ S_i\cup W=\operatorname{span}(S_i\cup W), $$
所以它 XOR-closed。
输出 $X=W\setminus C$。对于每个 $w\in W$：
- 如果 $w\notin C$，则 $w\in X$；
- 如果 $w\in C$，则 $w$ 本来就在每个 $S_i$ 中。
所以 $S_i\cup X=S_i\cup W$，答案合法。证毕。
引理 5
算法输出的操作数量最少。
根据引理 1，算法加入 $W$ 的每个独立向量都是任何合法答案所必需的。由于最终集合必须闭合，它们也必须包含这些向量张成的整个 $W$。
因此，对于每个 $w\in W\setminus C$，至少存在一个原集合不包含 $w$，任何合法答案都必须操作 $w$。
所以任何答案都至少包含 $W\setminus C$，而算法恰好输出它，故最优。证毕。
9. 复杂度
令
$$ M=\sum_i |S_i|. $$
时间复杂度为
$$ O(nm^2+Mm+2^m). $$
其中 $m\le 20$，可以通过。
空间复杂度为
$$ O(nm+M+2^m). $$