AT_arc155_e.[ARC155E] Split and Square

对于由非负整数组成的集合 $X$，我们定义 $f(X)$ 为：所有可以表示为 $X$ 中两个整数（可以是相同的整数）按位异或（$\mathrm{XOR}$）得到的非负整数组成的集合。例如，当 $X=\lbrace 1,\ 2,\ 4\rbrace$ 时，$f(X)=\lbrace 0,\ 3,\ 5,\ 6\rbrace$。

给定一个包含 $N$ 个小于 $2^M$ 的非负整数组成的集合 $S=\lbrace A_1,\ A_2,\ \dots,\ A_N\rbrace$。

你可以进行如下操作任意次：

• 将 $S$ 分成两个集合 $T_1$ 和 $T_2$（允许 $T_1$ 或 $T_2$ 为空集）。然后，用 $f(T_1)$ 与 $f(T_2)$ 的并集替换 $S$。

请你求出将 $S$ 变为 $\lbrace 0\rbrace$ 所需的最小操作次数。

按位异或（$\mathrm{XOR}$）运算的定义如下：对于非负整数 $A$、$B$，$A\oplus B$ 的二进制表示中，每一位 $2^k$（$k\geq 0$）上的数，如果 $A$ 和 $B$ 在该位上只有一个为 $1$，则该位为 $1$，否则为 $0$。

例如，$3\oplus 5=6$（二进制表示为 $011\oplus 101=110$）。
一般地，$k$ 个非负整数 $p_1,p_2,p_3,\dots,p_k$ 的按位异或定义为 $(\dots((p_1\oplus p_2)\oplus p_3)\oplus\dots\oplus p_k)$，并且可以证明其结果与顺序无关。

输入通过标准输入给出，格式如下：

$N$ $M$
$A_1$
$A_2$
$\vdots$
$A_N$

请输出答案。

限制条件

• $1\leq N\leq 300$
• $1\leq M\leq 300$
• $0\leq A_i<2^M$
• $A_i\ (1\leq i\leq N)$ 互不相同
• 每个 $A_i$ 都以恰好 $M$ 位的二进制形式给出（如果 $A_i$ 的二进制位数不足 $M$，则会补前导零）
• 所有输入均为整数

样例解释 1

第一次操作时，将 $T_1=\lbrace 0,1\rbrace$，$T_2=\lbrace 2,3\rbrace$，则 $f(T_1)=\lbrace 0,1\rbrace$，$f(T_2)=\lbrace 0,1\rbrace$，因此 $S$ 被替换为 $\lbrace 0,1\rbrace$。第二次操作时，将 $T_1=\lbrace 0\rbrace$，$T_2=\lbrace 1\rbrace$，则 $S=\lbrace 0\rbrace$。无法在少于 $2$ 次操作内将 $S$ 变为 $\lbrace 0\rbrace$，所以答案为 $2$。

样例解释 2

第一次操作时，将 $T_1=\lbrace 155\rbrace$，$T_2=\lbrace\rbrace$，则 $S$ 变为 $\lbrace 0\rbrace$。操作时允许 $T_1$ 或 $T_2$ 为空集。

样例解释 3

初始时 $S=\lbrace 0\rbrace$，无需进行任何操作。

由 ChatGPT 4.1 翻译