← 返回题目列表

Codeforces · 1977/D

D. 异或器

中文机器翻译题面 查看原题

给你一个二进制(仅由 0 和 1 组成)$$$n \times m$$$ 矩阵。您还可以使用 XORificator,使用它可以反转所选行中的所有值(即将 0 替换为 1,将 1 替换为 0)。

矩阵中的一列如果恰好包含一个 1,则被视为特殊列。您的任务是找到可以同时变为特殊的最大列数,以及应使用 XORificator 的行集来实现此目的。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 3 \cdot 10^5$$$, $$$n \cdot m \leq 3 \cdot 10^5$$$)。

测试用例的以下 $$$n$$$ 行中的每一行都包含长度为 $$$m$$$ 的二进制字符串。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出两行。

第一行,输出可能同时获取的最大特殊列数。

在第二行中,输出长度为 $$$n$$$ 的二进制字符串,其中,如果在第 $$$i$$$ 行上不使用异或器,则第 $$$i$$$ 字符为 0;如果在第 $$$i$$$ 行上使用异或器,则为 1。

如果有多个有效的 XORificator 配置可以实现最佳答案,则可以输出其中任何一个。

示例

输入 #1

5
3 4
1010
0110
0100
1 1
1
1 1
0
2 5
00101
10110
3 3
101
111
000

输出 #1

3
010
1
0
1
1
3
00
2
010

注意

在第一个测试用例中,您可以在第二行上使用 XORificator 使 $$$2$$$、$$$3$$$ 和 $$$4$$$ 列变得特殊。

在第二个测试用例中,唯一的列已经是特殊的,因此您不需要使用 XORificator。