← 返回题目列表

AtCoder · agc057_e

E. RowCol/ColRow 排序

中文机器翻译题面 查看原题

分数: 1400 点

问题陈述

考虑以下操作 H\times W 矩阵 A = (A_{i,j}) (1\leq i\leq H, 1\leq j\leq W).

  • 行排序:按升序对每一行进行排序。也就是说,排序 A_{i,1},\ldots,A_{i,W} 按升序排列每个 i.
  • 列排序:按升序对每列进行排序。也就是说,排序 A_{1,j},\ldots,A_{H,j} 按升序排列每个 j.

您将获得 H\times W 矩阵 B = (B_{i,j})。找出数量 H\times W 矩阵 A 满足以下两个条件,模 998244353.

  • 执行行排序然后列排序 A 产生 B.
  • 执行列排序然后行排序 A 产生 B.

约束

  • 1\leq H, W\leq 1500
  • 0\leq B_{i,j}\leq 9
  • B_{i,j}\leq B_{i,j+1},对于任何 1\leq i\leq H 和 1\leq j\leq W - 1.
  • B_{i,j}\leq B_{i+1,j},对于任何 1\leq j\leq W 和 1\leq i\leq H - 1.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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

2 2
0 0
1 2

示例输出 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

3 3
0 1 3
2 4 7
5 6 8

示例输出 2

576

\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}.


示例输入 3

3 5
0 0 0 1 1
0 0 1 1 2
0 1 1 2 2

示例输出 3

10440

示例输入 4

1 7
2 3 3 6 8 8 9

示例输出 4

1260