CF2053F.Earnest Matrix Complement

Aquawave 有一个大小为 $ n \times m $ 的矩阵 $ A $，其中的元素只允许是 $ [1, k] $ 区间内的整数。矩阵中的一些位置已被填上整数，其余位置用 $ -1 $ 表示，代表尚未填充。

你的任务是将矩阵 $ A $ 填满所有空白位置，接着定义 $ c_{u,i} $ 为第 $ i $ 行中数字 $ u $ 出现的次数。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 $ 行，每行包含 $ 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 $。

对于每个测试用例，输出一个整数，表示最大可能的美丽值。

在第一个测试用例中，矩阵 $ 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}.$$

本翻译由 AI 自动生成