← 返回题目列表

AtCoder · arc107_c

C. 随机排列

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

分数: 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