简要题意

给定包含 $N$ 个长度为 $M$ 的 01 串的集合 $S$，有 $Q$ 组询问，每个询问给出一个长度为 $M$ 的 01 串 $t_i$，求集合 $$\left\{u\in \mathbb{Z}_2^M\left|\exists T\subseteq S,\ \mathrm{s.t.}\ u = t_i \oplus \bigoplus_{v\in T} v\right.\right\}$$ 中，对应位为 $1$ 的下标序列的字典序最小的 01 串。

$1\le N, M, k\le 2000$

题解

字典序

处理最小化字典序问题，一个经典思路是按位贪心。在本题中，由于需要最小化的串长不固定，故贪心思路为：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应使第一个为 $1$ 的下标尽可能小。
• 在确定第一个 $1$ 的下标后，检查是否可以将后缀全部变成 $0$，如果可以则输出；否则，应使第二个为 $1$ 的下标尽可能小。
• $\ldots$

上述贪心等价于：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应尽量使第 1 位为 $1$。
• 如果确定第 1 位后，从第 2 位起可以为全零，则输出；否则，应尽量使第 12 位为 $1$。
• $\ldots$

我会线性基

因为涉及到异或，不难想到用线性基来处理本题。假设我们已经将 $S$ 处理成了相应的基向量。

对于每个询问，首先把所有主元清零，使得询问串最多只有自由元的位置非零。如果此时询问串变成全零串，则答案即为全零串。

否则，按主元顺序处理每个基向量。需要再次异或上一个基向量，当且仅当异或可以使询问串主元对应位置变成 $1$（也即此时询问串主元位置为 $0$）。特别地，如果异或完，主元位置之后变成全零，则答案即为当前串。

使用 bitset 处理，复杂度即为 $O(NMQ/w)$, 其中 $w$ 表示 bitset 位长。

除上述做法以外，还有各种使用线性基的处理方式，在此不详细展开。

不推荐考场实现的做法（简要版）

得到线性基之后，可以考虑补充没有主元对应的标准基，这样可以得到 $\mathbb{Z}_2^M$ 的一组基 $B$。将询问在 $B$ 下分解，则答案为全零串当且仅当补充的标准基的系数为 $0$。

检查完一个 $S$ 的主元位置 $x$ 后，如果这一位之后没有非零自由元，则输出当前串；否则，为了在子空间 $\mathbb{Z}_2^{M-x}$ 中处理询问串的后 $(M-x)$ 位，需要将 $x$ 对应的基向量（去掉主元的 $1$ 之后）在该子空间中重新分解，更新系数。