← 返回题目列表

Codeforces · 1993/E

E. 异或网格问题

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

给定一个大小为 $$$n \times m$$$ 的矩阵 $$$a$$$,其中每个单元格包含一个非负整数。矩阵第 $$$i$$$ 行和第 $$$j$$$ 列的交集处的整数称为 $$$a_{i,j}$$$。

让我们分别将 $$$f(i)$$$ 和 $$$g(j)$$$ 定义为第 $$$i$$$ 行和第 $$$j$$$ 列中所有整数的异或。在一次操作中,您可以:

- 选择任意行 $$$i$$$,然后为每个 $$$1 \le j \le m$$$ 分配 $$$a_{i,j} := g(j)$$$;或
- 选择任意列 $$$j$$$,然后为每个 $$$1 \le i \le n$$$ 分配 $$$a_{i,j} := f(i)$$$。

对矩阵的 $$$2$$$ 列应用运算的示例。

在此示例中,当我们对 $$$2$$$ 列应用操作时,该列中的所有元素都会更改:

- $$$a_{1,2} := f(1) = a_{1,1} \oplus a_{1,2} \oplus a_{1,3} \oplus a_{1,4} = 1 \oplus 1 \oplus 1 \oplus 1 = 0$$$
- $$$a_{2,2} := f(2) = a_{2,1} \oplus a_{2,2} \oplus a_{2,3} \oplus a_{2,4} = 2 \oplus 3 \oplus 5 \oplus 7 = 3$$$
- $$$a_{3,2} := f(3) = a_{3,1} \oplus a_{3,2} \oplus a_{3,3} \oplus a_{3,4} = 2 \oplus 0 \oplus 3 \oplus 0 = 1$$$
- $$$a_{4,2} := f(4) = a_{4,1} \oplus a_{4,2} \oplus a_{4,3} \oplus a_{4,4} = 10 \oplus 11 \oplus 12 \oplus 16 = 29$$$

您可以多次应用这些操作。然后,我们通过求和所有相邻单元对之间的绝对差来计算最终矩阵的 $$$\textit{beauty}$$$。

更正式地说,$$$\textit{beauty}(a) = \sum|a_{x,y} - a_{r,c}|$$$ 对于所有单元格 $$$(x, y)$$$ 和 $$$(r, c)$$$(如果它们相邻)。如果两个单元共用一条边,则认为它们是相邻的。

在所有可获得的矩阵中找到最小 $$$\textit{beauty}$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 250$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 15$$$) - 分别是 $$$a$$$ 的行数和列数。

接下来的 $$$n$$$ 行,每行包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$0 \le a_{i,j} < 2^{20}$$$) - 矩阵 $$$a$$$ 的描述。

保证所有测试用例的 $$$(n^2 + m^2)$$$ 总和不超过 $$$500$$$。

输出

对于每个测试用例,打印一个整数 $$$b$$$ — 矩阵的最小可能 $$$\textit{beauty}$$$。

示例

输入 #1

4
1 2
1 3
2 3
0 1 0
5 4 4
2 3
0 2 4
4 5 1
3 3
1 2 3
4 5 6
7 8 9

输出 #1

1
3
13
24

注意

我们将 $$$r(i)$$$ 表示为应用于第 $$$i$$$ 行的第一个类型操作,将 $$$c(j)$$$ 表示为应用于第 $$$j$$$ 列的第二个类型操作。

在第一个测试用例中,您可以应用操作 $$$c(1)$$$,该操作分配 $$$a_{1,1} := 1 \oplus 3 = 2$$$。然后,我们将收到这个矩阵:

23

在第二个测试用例中,您可以应用操作 $$$r(1)$$$,它分配:

- $$$a_{1,1} := g(1) = 0 \oplus 5 = 5$$$
- $$$a_{1,2} := g(2) = 1 \oplus 4 = 5$$$
- $$$a_{1,3} := g(3) = 0 \oplus 4 = 4$$$

执行运算后得到的矩阵为:

554544

在第三个测试用例中,实现最小 $$$\textit{beauty}$$$ 的最佳方法是应用三个操作:$$$c(3)$$$、$$$r(2)$$$ 和 $$$c(2)$$$。得到的矩阵是:

046456