分数: 500 点
问题陈述
给定的是 N \times N 矩阵和一个整数 K中的条目 i第行和 j该矩阵的第列表示为 a_{i, j}。该矩阵包含每个 1, 2, \dots, N^2 恰好一次。
Sigma可以重复以下两种操作 任意 以任意顺序多次。
- 选择两个整数 x, y (1 \leq x < y \leq N) 满足 a_{i, x} + a_{i, y} \leq K 对于所有人 i (1 \leq i \leq N)并交换 x-th 和 y- 第列。
- 选择两个整数 x, y (1 \leq x < y \leq N) 满足 a_{x, i} + a_{y, i} \leq K 对于所有人 i (1 \leq i \leq N)并交换 x-th 和 y第行。
通过这些运算他能得到多少个矩阵?求模 998244353.
约束
- 1 \leq N \leq 50
- 1 \leq K \leq 2 \times N^2
- a_{i, j}是以下内容的重新排列 1, 2, \dots, N^2.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
a_{1, 1} a_{1, 2} ... a_{1, N}
a_{2, 1} a_{2, 2} ... a_{2, N}
:
a_{N, 1} a_{N, 2} ... a_{N, N}
输出
打印 Sigma 可以求模的矩阵数量 998244353.
示例输入 1
3 13 3 2 7 4 8 9 1 6 5
示例输出 1
12
例如,Sigma 可以通过设置交换两列 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
示例输入 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