P13052 [GCJ 2020 Qualification] Indicium

Indicium 在拉丁语中意为"迹"。本题中我们将研究拉丁方阵及其矩阵迹。 一个拉丁方阵是指 $\mathbf{N} \times \mathbf{N}$ 的方阵，其中每个单元格包含 $\mathbf{N}$ 个不同值之一，且每行每列都不重复出现相同值。在本题中，我们仅处理"自然拉丁方阵"，即这些 $\mathbf{N}$ 个值为 1 到 $\mathbf{N}$ 的整数。 方阵的迹是指主对角线（从左上到右下）上所有值的和。 给定 $\mathbf{N}$ 和 $\mathbf{K}$，构造任意一个迹为 $\mathbf{K}$ 的 $\mathbf{N} \times \mathbf{N}$ 自然拉丁方阵，或判定其不存在。例如，以下是 $\mathbf{N}=3, \mathbf{K}=6$ 时的两种可能解（贡献迹的值已加下划线）： $\begin{array}{lll} \underline{2} & 1 & 3 \\ 3 & \underline{2} & 1 \\ 1 & 3 & \underline{2} \end{array} \quad \begin{array}{lll} \underline{3} & 1 & 2 \\ 1 & \underline{2} &3 \\ 2 & 3 & \underline{1} \end{array}$

输入第一行包含测试用例数 $\mathbf{T}$。随后 $\mathbf{T}$ 行，每行包含两个整数 $\mathbf{N}$ 和 $\mathbf{K}$，分别表示方阵大小和期望的迹。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 `IMPOSSIBLE`（无解时）或 `POSSIBLE`（有解时）。若有解，还需输出 $\mathbf{N}$ 行，每行 $\mathbf{N}$ 个整数表示满足条件的自然拉丁方阵。

**样例解释** 样例 #1 对应题目描述中的情况。 样例 #2 无解。所有可能的 2×2 自然拉丁方阵如下： ``` 1 2 2 1 2 1 1 2 ``` 它们的迹分别为 2 和 4，无法得到迹 3。 **数据范围** - $\mathrm{N} \leqslant \mathrm{K} \leqslant \mathrm{N}^{2}$ **测试集 1（7 分，可见判果）** - $\mathrm{T}=44$ - $2 \leqslant \mathrm{N} \leqslant 5$ **测试集 2（25 分，隐藏判果）** - $1 \leqslant \mathrm{T} \leqslant 100$ - $2 \leqslant \mathrm{N} \leqslant 50$ 翻译由 DeepSeek V3 完成