QOJ.ac

QOJ

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100

#12007. 矩阵求逆

統計

你有一个 $N \times N$ 的网格棋盘,初始为空。你需要向每个格子中填入一个整数,使得 $1$ 到 $N^2$ 的每个整数恰好出现一次。令 $M_{i,j}$ 为从上往下第 $i$ 行、从左往右第 $j$ 列的格子中填入的整数。

定义序列 $A$ 和 $B$ 如下: $A = M_{1,1}, M_{1,2}, \dots, M_{1,N}, M_{2,1}, M_{2,2}, \dots, M_{2,N}, \dots, M_{N,N}$ $B = M_{1,1}, M_{2,1}, \dots, M_{N,1}, M_{1,2}, M_{2,2}, \dots, M_{N,2}, \dots, M_{N,N}$

例如,当棋盘如下所示时: 1 3 4 2 7 6 9 8 5

序列 $A$ 和 $B$ 定义如下: $A = 1, 3, 4, 2, 7, 6, 9, 8, 5$ $B = 1, 2, 9, 3, 7, 8, 4, 6, 5$

给定整数 $N, X, Y$,请找到一种填数方式,使得序列 $A$ 和 $B$ 的逆序对数量分别为 $X$ 和 $Y$,或者报告不存在这样的方案。

说明:序列 $C = c_1, c_2, \dots, c_{N \times N}$ 的逆序对数量是指满足 $i < j$ 且 $c_i > c_j$ 的数对 $(i, j)$ 的个数。

输入格式

输入通过标准输入给出,格式如下:

$N \ X \ Y$

数据范围

  • $2 \le N \le 300$
  • $0 \le X, Y \le \frac{N^2(N^2-1)}{2}$

输出格式

如果不存在解,输出 No。 否则,按以下格式输出答案: Yes $M_{1,1} \ M_{1,2} \dots \ M_{1,N}$ $M_{2,1} \ M_{2,2} \dots \ M_{2,N}$ $\vdots$ $M_{N,1} \ M_{N,2} \dots \ M_{N,N}$

如果存在多种解,输出其中任意一种即可。

样例

样例输入 1

3 8 13

样例输出 1

Yes
1 3 4
2 7 6
9 8 5

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.