P14022 [ICPC 2024 Nanjing R] Bingo

给定两个整数 $n$ 和 $m$，以及一个长度为 $n \times m$ 的整数序列 $a_1, a_2, \cdots, a_{nm}$，我们将用序列里的数字填入一个 $n$ 行 $m$ 列的网格。具体来说，令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子，我们会将序列里的第 $((i - 1) \times m + j)$ 个数（也就是 $a_{(i - 1) \times m + j}$）填入那个格子中。 称整数 $k$ 是序列的 “bingo 整数”，若将所有数字填入格子后，以下两个条件至少满足一个。 - 至少存在一行，使得那一行所有格子里的整数都小于等于 $k$。 - 至少存在一列，使得那一列所有格子里的整数都小于等于 $k$。 容易发现，一个序列可以有很多 bingo 整数。不过本题中，我们只对最小的 bingo 整数感兴趣。 对于给定序列的所有 $(nm)!$ 个排列，求每个排列的最小 bingo 整数之和。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$，$1 \le n \times m \le 2 \times 10^5$），表示网格的行数和列数。 第二行输入 $n \times m$ 个整数 $a_1, a_2, \cdots, a_{nm}$（$0 \le a_i < 998\,244\,353$）表示给定序列。 保证所有数据 $n \times m$ 之和不超过 $4 \times 10^5$。

每组数据输出一行一个整数表示答案。

对于第一组样例数据，如果 $1$ 和 $2$ 不在同一行或同一列，那么最小 bingo 整数就是 $3$，否则最小 bingo 整数就是 $2$。在 $8$ 个排列中，$1$ 和 $2$ 不在同一行或同一列，所以答案是 $8 \times 3 + (4! - 8) \times 2 = 56$。 对于第二组样例数据，最小 bingo 整数总是 $10$，所以答案是 $3! \times 10 = 60$。