← 返回题目列表

Codeforces · 2053/F

F. 认真的矩阵补集

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

- Peter:好消息:我的问题 T311013 已获得批准!
- $$$\delta$$$:我很高兴我的电脑没电了,这样我就不会参加 wyrqwq 的回合并获得负 delta。
- Felix:[thumbs_up] 关于已删除歌曲的问题陈述!
- Aquawave:我会哀悼我的化学反应吗?
- E.Space:啊?
- Trine:面包。
- Iris:那么为什么我总是测试问题呢?

时间会过去,我们可能会再次见面。回望过去,每个人都过上了自己想要的生活。

Aquawave 有一个大小为 $$$n\times m$$$ 的矩阵 $$$A$$$,其元素只能是 $$$[1, k]$$$(含)范围内的整数。在矩阵中,一些单元格已经填充了整数,而其余单元格目前尚未填充,用$$$-1$$$表示。

您将填写 $$$A$$$ 中所有未填写的位置。之后,令 $$$c_{u,i}$$$ 为元素 $$$u$$$ 在第 $$$i$$$ 行中出现的次数。 Aquawave 将矩阵之美定义为

$$$$$$\sum_{u=1}^k \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1}.$$$$$$

你必须在最佳填空后找到$$$A$$$的最大可能的美丽。

输入

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

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$, $$$2 \leq m \leq 2\cdot 10^5$$$, $$$n \cdot m \leq 6\cdot 10^5$$$, $$$1 \leq k \leq n\cdot m$$$) - 分别是矩阵 $$$A$$$ 的行数和列数,以及矩阵中整数的范围。

然后是 $$$n$$$ 行,第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$A_{i,1},A_{i,2},\ldots,A_{i,m}$$$ ($$$1 \leq A_{i,j} \leq k$$$ 或 $$$A_{i,j} = -1$$$) — $$$A$$$ 中的元素。

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

输出

对于每个测试用例,输出一个整数——最大可能的美感。

示例

输入 #1

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

输出 #1

4
4
10
10
8
102
93
58
13

注意

在第一个测试用例中,矩阵 $$$A$$$ 已经确定。它的美在于

$$$$$$\sum_{u=1}^k \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1} = c_{1,1}\cdot c_{1,2} + c_{1,2}\cdot c_{1,3} + c_{2,1}\cdot c_{2,2} + c_{2,2}\cdot c_{2,3} + c_{3,1}\cdot c_{3,2} + c_{3,2}\cdot c_{3,3} = 1\cdot 1 + 1\cdot 1 + 2\cdot 0 + 0\cdot 1 + 0\cdot 2 + 2\cdot 1 = 4.$$$$$$

在第二个测试用例中,可以按如下方式填充矩阵:

$$$$$$ \begin{bmatrix} 2 &3 &3 \\ 2 &2 &3 \end{bmatrix}, $$$$$$

并获取值 $$$4$$$。可以证明,这是所能得到的最大可能答案。

在第三个测试用例中,可能的最佳配置之一是:

$$$$$$ \begin{bmatrix} 1 &1 &1 \\ 1 &2 &1 \\ 1 &1 &4 \end{bmatrix}。 $$$$$$

在第四个测试用例中,可能的最佳配置之一是:

$$$$$$ \begin{bmatrix} 1 &3 &2 &3 \\ 1 &3 &2 &1 \\ 3 &1 &5 &1 \end{bmatrix}。 $$$$$$

在第五个测试用例中,可能的最佳配置之一是:

$$$$$$ \begin{bmatrix} 5 &5 &2 \\ 1 &8 &5 \\ 7 &5 &6 \\ 7 &7 &4 \\ 4 &4 &4 \end{bmatrix}。 $$$$$$