AT_agc057_e.[AGC057E] RowCol/ColRow Sort

给定一个 $H\times W$ 的矩阵 $A = (A_{i,j})$（$1\leq i\leq H,\ 1\leq j\leq W$），定义如下两种操作：

• 行排序：对每一行进行升序排序。即对于所有 $i$，将 $A_{i,1},\ldots,A_{i,W}$ 升序排列。
• 列排序：对每一列进行升序排序。即对于所有 $j$，将 $A_{1,j},\ldots,A_{H,j}$ 升序排列。

给定一个 $H\times W$ 的矩阵 $B = (B_{i,j})$，请计算满足以下两个条件的 $H\times W$ 矩阵 $A$ 的总数，并对 $998244353$ 取模：

• 对 $A$ 先进行行排序再进行列排序，结果等于 $B$。
• 对 $A$ 先进行列排序再进行行排序，结果等于 $B$。

输入通过标准输入给出，格式如下：

$H$ $W$
$B_{1,1}$ $B_{1,2}$ $\ldots$ $B_{1,W}$
$\vdots$
$B_{H,1}$ $B_{H,2}$ $\ldots$ $B_{H,W}$

输出满足条件的矩阵 $A$ 的总数，对 $998244353$ 取模后的结果。

限制条件

• $1\leq H,\ W\leq 1500$
• $0\leq B_{i,j}\leq 9$
• 对任意 $1\leq i\leq H$ 及 $1\leq j\leq W-1$，有 $B_{i,j}\leq B_{i,j+1}$
• 对任意 $1\leq j\leq W$ 及 $1\leq i\leq H-1$，有 $B_{i,j}\leq B_{i+1,j}$
• 输入的所有值均为整数

样例解释 1

满足条件的矩阵有如下 $4$ 个：$\begin{pmatrix}0&0\\1&2\end{pmatrix}$，$\begin{pmatrix}0&0\\2&1\end{pmatrix}$，$\begin{pmatrix}1&2\\0&0\end{pmatrix}$，$\begin{pmatrix}2&1\\0&0\end{pmatrix}$。例如，$\begin{pmatrix}2&1\\0&0\end{pmatrix}$ 满足条件的验证如下：

• 先行排序再列排序：$\begin{pmatrix}2&1\\0&0\end{pmatrix}\to\begin{pmatrix}1&2\\0&0\end{pmatrix}\to\begin{pmatrix}0&0\\1&2\end{pmatrix}$。
• 先列排序再行排序：$\begin{pmatrix}2&1\\0&0\end{pmatrix}\to\begin{pmatrix}0&0\\2&1\end{pmatrix}\to\begin{pmatrix}0&0\\1&2\end{pmatrix}$。

样例解释 2

例如 $\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}$ 满足条件，验证如下：

• 先行排序再列排序：$\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}\to\begin{pmatrix}5&6&7\\0&1&3\\2&4&8\end{pmatrix}\to\begin{pmatrix}0&1&3\\2&4&7\\5&6&8\end{pmatrix}$。
• 先列排序再行排序：$\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}\to\begin{pmatrix}3&0&1\\4&7&2\\5&8&6\end{pmatrix}\to\begin{pmatrix}0&1&3\\2&4&7\\5&6&8\end{pmatrix}$。

由 ChatGPT 4.1 翻译