CF2053F Earnest Matrix Complement

3, 2, 1, ... 我们是 —— RiOI 团队！ —— Felix & All, [特别感谢 3](https://www.luogu.com.cn/problem/T351681) - Peter: 好消息，我的题目 T311013 已获批！ - $ \delta $: 幸好我的电脑没电，不然我可能参加了 wyrqwq 的比赛并得到负分。 - Felix: \[点赞\] 关于一首被删除歌曲的题目陈述！ - Aquawave: 我该为我的化学课感到悲伤吗？ - E.Space: 啊？ - Trine: 面包。 - Iris: 为什么总是我来测试题目？ 时光走过，未来我们会再遇见。回首往事，大家都过上了各自想要的生活。

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 自动生成**