CF1466F Euclid's nightmare

给定包含 $n$ 个 $m$ 维向量的向量集 $S$，每个向量 $\overrightarrow{a}$ 满足 $a_i\in \{0,1\}$ 且 $\sum\limits_{i=1}^ma_i\in\{1,2\}$。定义向量加法 $\overrightarrow{c}=\overrightarrow{a}+\overrightarrow{b}$ 为 $\forall i\in \Z\cap[1,m], c_i=a_i\oplus b_i$，其中 $\oplus$ 表示异或运算。 求极大线性空间 $T$ 使得 $T$ 的一组基 $A$ 均为 $S$ 中元素。输出 $|T|,|A|$ 以及 $A$。 要求在 $|A|$ 最小前提下 $A$ 关于向量编号字典序最小。

无

无

In the first example we are given three vectors: - $ 10 $ - $ 01 $ - $ 11 $ It turns out that we can represent all vectors from our $ 2 $ -dimensional space using these vectors: - $ 00 $ is a sum of the empty subset of above vectors; - $ 01 = 11 + 10 $ , is a sum of the first and third vector; - $ 10 = 10 $ , is just the first vector; - $ 11 = 10 + 01 $ , is a sum of the first and the second vector. Hence, $ T = \{00, 01, 10, 11\} $ . We can choose any two of the three vectors from $ S $ and still be able to obtain all the vectors in $ T $ . In such a case, we choose the two vectors which appear first in the input. Since we cannot obtain all vectors in $ T $ using only a single vector from $ S $ , $ |S'| = 2 $ and $ S' = \{10, 01\} $ (indices $ 1 $ and $ 2 $ ), as set $ \{1, 2 \} $ is lexicographically the smallest. We can represent all vectors from $ T $ , using only vectors from $ S' $ , as shown below: - $ 00 $ is a sum of the empty subset; - $ 01 = 01 $ is just the second vector; - $ 10 = 10 $ is just the first vector; - $ 11 = 10 + 01 $ is a sum of the first and the second vector.