CF1085G Beautiful Matrix
题目描述
Petya 收集漂亮矩阵。
一个大小为 $n \times n$ 的矩阵是漂亮的，当且仅当满足以下条件：
- 矩阵的所有元素都是 $1$ 到 $n$ 之间的整数；
- 对于矩阵的每一行，该行所有元素互不相同；
- 对于每一对垂直相邻的元素（即上下相邻的元素），这两个元素不同。
今天 Petya 购买了一个大小为 $n \times n$ 的漂亮矩阵 $a$，现在他想确定它的稀有度。
矩阵的稀有度定义为：在按字典序排序的所有大小为 $n \times n$ 的漂亮矩阵列表中，该矩阵的索引。矩阵的比较按行逐行进行（字典序最小的矩阵索引为零）。
由于漂亮矩阵的数量可能非常庞大，Petya 希望你计算矩阵 $a$ 的稀有度对 $998\,244\,353$ 取模的结果。
输入格式
第一行包含一个整数 $n$（$1 \le n \le 2000$）——矩阵 $a$ 的行数和列数。
接下来 $n$ 行，每行包含 $n$ 个整数 $a_{i,j}$（$1 \le a_{i,j} \le n$）——矩阵 $a$ 的元素。
保证 $a$ 是一个漂亮矩阵。
输出格式
输出一个整数——矩阵 $a$ 的稀有度对 $998\,244\,353$ 取模后的结果。
说明/提示
大小为 $2 \times 2$ 的漂亮矩阵只有 2 个：
以下是按字典序排列的大小为 $3 \times 3$ 的前 5 个漂亮矩阵：
翻译由 DeepSeek R1 完成