P10567 题解
蟋蟀喵～～
·
·
题解
题目
小 A 给了你一个边长为
在填之前，你想知道是否有任何一种解法满足上述条件，如果可以，输出 `Yes`；否则，输出 `No`。
### 分析
赛时，我先看了看样例，样例有四个数据，$n$ 为偶数时输出的都是 `Yes`，为奇数时输出的都为 `No`，所以这道题的解法会不会和奇偶性相关呢？
先考虑 $n$ 为奇数的情况。
首先，我们要明白一个小学数学常识：
- 奇数个奇数相加，和为奇数。
- 奇数个偶数相加，和为偶数。
- 偶数个奇数相加，和为偶数。
- 偶数个偶数相加，和为偶数。
我们假设 $n$ 为奇数时存在一个合法的网格，根据题目，该网格有 $n$ 列，每列和是偶数，所以
$$\sum_{i = 1}^{n^2}i$$
也应为偶数（该网格包含了 $1 \sim n \times n$ 中的所有数，共 $n$ 列，每列和为偶数）。
但我们知道，该网格有 $n$ 行，每行和为奇数，所以
$$\sum_{i = 1}^{n^2}i$$
为奇数。
**矛盾。**
故 $n$ 为奇数时无论如何都不存在合法网格。
再考虑 $n$ 为偶数的情况。
$n$ 为偶数时，$n^2$ 也为偶数，即 $1 \sim n \times n$ 中奇数和偶数数量相等，所以可以证明，当 $n$ 为偶数时，一定可以构造出至少一种合法的排列方式。
#### 构造方法
若 ${\frac{n}{2}}$ 不为 $2$ 的倍数，直接将 $1 \sim n ^ 2$ 顺序排列即可；若 ${\frac{n}{2}}$ 为 $2$ 的倍数，需将 $1 \sim n ^ 2$ 顺序排列后将第一行的最后一个数与第二行的第一个数进行交换、第三行的最后一个数与第四行的第一个数进行交换，以此类推。
示例：
$n = 2$ 时：
$$
\begin{bmatrix}
1 & 2 \\
3 & 4 \\
\end{bmatrix}
$$
$n = 4$ 时：
$$
\begin{bmatrix}
1 & 2 & 3 & 5 \\
4 & 6 & 7 & 8 \\
9 & 10 & 11 & 13 \\
12 & 14 & 15 & 16
\end{bmatrix}
$$
### 结论：
$n$ 为奇数时输出 `No`，$n$ 为偶数时输出 `Yes`。