D 再无数据结构

时间限制: 1s
内存限制: 待定 MB

题目描述

给定一个 $n \times m$ 的矩阵 $a$ 和正整数 $k$，矩阵的每个值是 $[0,k]$ 的整数。你需要把每个 $a_{i,j}$ 都改成 $[1,k]$ 中的整数，最大化下式的值：

$$\sum_{x=1}^{n-1}\sum_{y=1}^{m}\sum_{z=1}^{m}[a_{x,y} = a_{x+1,z}]$$

其中当 $[P]$ 是一个条件是，$[P]=1$ 当且仅当 $P$ 成立，否则 $[P]=0$。即上式表示有多少对正整数$(x,y,z)$满足 $a_{x,y}=a_{x+1,z}$。

输入格式

第一行一个正整数 $T$ 表示数据组数。

对于每一组测试数据，第一行三个正整数 $n,m,k$，后 $n$ 行每行 $m$ 个非负整数表示矩阵 $a$。

输出格式

对于每组测试数据，输出一行一个非负整数表示答案的最大值。

输入输出样例

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

4
10
10
8
102

样例解释

对于第一组测试数据，直接计算可得所求值为 $4$。

对于第二组测试数据，可以把所有 $0$ 都改成 $1$，计算所求值为 $10$。

对于第三组测试数据，可以把三个 $0$ 分别改成 $1,3,1$，计算所求值为 $10$。

对于第四组测试数据，可以把四个 $0$ 分别改成 $5,5,7,4$（从上到下），计算所求值为 $8$。

注意事项

1. 本场比赛输入量普遍较大，请使用较快的读入方式。
2. 每题都有大样例，强度还不错。
3. 保证所有模数都没有意义。
4. 保证没有意义不明的话。
5. 如果不幸找到原题，请不要声张，闷声发大财。
6. 这并不是数据结构场。
7. 保证题目数量不是质数。
8. 保证每个前缀的题目的样例个数和都是质数（意义不明）。
9. 具体时限暂以 pdf 为准，赛时可能更新。
10. 后面忘了。