CF1360H Binary Median

考虑所有长度为 $m$ 的二进制字符串（$1 \le m \le 60$）。二进制字符串是仅由字符 $0$ 和 $1$ 组成的字符串。例如，0110 是二进制字符串，而 012aba 不是。显然，这样的字符串总共有 $2^m$ 个。 如果字符串 $s$ 在第一个不同的位置 $i$ 满足 $s[i] < t[i]$，则称字符串 $s$ 在字典序上小于字符串 $t$（两者长度均为 $m$）。这正是字典以及大多数现代编程语言中标准的字符串比较方式。例如，字符串 01011 在字典序上小于字符串 01100，因为前两个字符相同，而第三个字符在第一个字符串中小于第二个字符串中的对应字符。 现在，从这个集合中移除 $n$ 个（$1 \le n \le \min(2^m-1, 100)$）互不相同的长度为 $m$ 的二进制字符串 $a_1, a_2, \ldots, a_n$。因此，剩下的字符串数量为 $k=2^m-n$。将剩下的所有字符串按字典序升序排列。 将排序后的所有字符串从 $0$ 到 $k-1$ 编号。请输出编号为 $\lfloor \frac{k-1}{2} \rfloor$ 的字符串（这样的元素称为中位数），其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整。 例如，如果 $n=3$，$m=3$，$a=[010, 111, 001]$，则移除 $a_i$ 后并排序，结果为 $[000, 011, 100, 101, 110]$。因此，所求的中位数为 100。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每组测试用例的第一行包含两个整数 $n$（$1 \le n \le \min(2^m-1, 100)$）和 $m$（$1 \le m \le 60$），分别表示要移除的字符串数量和二进制字符串的长度。接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串 $a_1, a_2, \ldots, a_n$，它们互不相同。 所有测试用例中给出的二进制字符串的总长度不超过 $10^5$。

输出 $t$ 行，每行对应一个测试用例的答案。对于每个测试用例，输出一个长度为 $m$ 的字符串，即对应剩余字符串集合排序后的中位数。

第一个测试用例的解释见题面。 第二个测试用例中，移除字符串并排序后，结果为 $[001, 010, 101, 110]$。因此，所求的中位数为 010。 由 ChatGPT 4.1 翻译