AT_arc107_c.[ARC107C] Shuffle Permutation

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $N \times N$ 的矩阵和一个整数 $K$ 。该矩阵的第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$ 。这个矩阵包含了 $1, 2, \dots, N^2$ 的所有数，每个数恰好出现一次。

sigma 君可以按任意顺序、任意次数进行以下两种操作：

对于所有 $i$ （ $1 \leq i \leq N$ ），如果存在 $x, y$ （ $1 \leq x < y \leq N$ ）使得 $a_{i,x} + a_{i,y} \leq K$ ，则可以交换矩阵的第 $x$ 列和第 $y$ 列。
对于所有 $i$ （ $1 \leq i \leq N$ ），如果存在 $x, y$ （ $1 \leq x < y \leq N$ ）使得 $a_{x,i} + a_{y,i} \leq K$ ，则可以交换矩阵的第 $x$ 行和第 $y$ 行。

问最终能够得到多少种不同的矩阵？请输出答案对 $998244353$ 取模后的结果。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $a_{1,1}$ $a_{1,2}$ $\dots$ $a_{1,N}$ $a_{2,1}$ $a_{2,2}$ $\dots$ $a_{2,N}$ $\dots$ $a_{N,1}$ $a_{N,2}$ $\dots$ $a_{N,N}$

输出格式

输出最终能够得到的不同矩阵的种数，对 $998244353$ 取模。

输入输出样例

输入#1
```
3 13
3 2 7
4 8 9
1 6 5
```
输出#1
```
12
```

输入#2

10 165
82 94 21 65 28 22 61 80 81 79
93 35 59 85 96 1 78 72 43 5
12 15 97 49 69 53 18 73 6 58
60 14 23 19 44 99 64 17 29 67
24 39 56 92 88 7 48 75 36 91
74 16 26 10 40 63 45 76 86 3
9 66 42 84 38 51 25 2 33 41
87 54 57 62 47 31 68 11 83 8
46 27 55 70 52 98 20 77 89 34
32 71 30 50 90 4 37 95 13 100

输出#2

348179577

说明/提示

限制条件

$1 \leq N \leq 50$
$1 \leq K \leq 2N^2$
$a_{i,j}$ 是 $1, 2, \dots, N^2$ 的一个排列
输入的所有数均为整数

样例解释 1

例如，可以选择 $x=1, y=2$ 交换列向量，得到如下矩阵：

2 3 7
8 4 9
6 1 5

之后再选择 $x=1, y=3$ 交换行向量，得到如下矩阵：

6 1 5
8 4 9
2 3 7

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页