T30179: 数字华容道（Hard Version）

Cycle Decomposition, http://cs101.openjudge.cn/practice/30179/

总时间限制：1000ms，单个样例点时间限制：500ms，内存限制：65536kB

数字华容道的游戏玩法：在一个 $n\times n$ 的方格中放置 $1$ 到 $n^2-1$ 的所有数字（每个数字占据一空间），剩下一个空格（输入中用 $0$ 表示）。每次可以将与空格相邻的几个数字平移到空格处。游戏目标是尽可能快的将给定盘面还原到初始状态。（初始状态就是 $1$ 到 $n^2-1$ 按顺序填充每一行，空格在右下角的盘面） 例如一个可能的初始盘面是：

1 2 3 4
5 6 7 8
9 10 11 12
15 13 14 0

你的目标是通过平移数字，将盘面变成

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

的样子。

一天，小K正准备玩数字华容道，但是他不小心把盘面中的数字小方格都打翻在地了。虽然他将所有的数字都乱序排入了盘面中，但是这样的盘面是不一定有解的，所以他想请你判断一下这个盘面是否有解。

输入

第 $1$ 行：一个整数 $t$ ，$(1\le t\le 100)$，表示样例数目。 接下来对于每个样例： 第 $1$ 行：一个整数 $n$ ，$(2\le n\le 1000)$ 。（你就不要问小K是怎么把一百万个小方格捡起来的了） 第 $2$ 行到第 $n+1$ 行： $n$ 个整数，表示盘面。 数据保证每一个测试点都有 $max(n^2)\times t\le {10}^7$。

输出

输出 $t$ 行。对于每一个样例，如果盘面有解，输出yes，否则输出no

样例输入

2
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
2
2 1
3 0

样例输出

yes
no

（注：此题与Easy Version唯一的不同之处在于Hard Version的每一个输入文件都有多个样例，而Easy Version只有一个。）

提示：

tags: math, cycle decomposition hint: 一个经典的智力问题。 现在有100个囚犯被囚禁，典狱长准备和他们玩一个游戏：有一百张写有 $1-100$ 号码的纸条被倒扣在一百个编号 $1-100$ 的盒子中。每个囚犯可以打开 $50$ 个盒子，但是所有囚犯在打开完盒子后不能与其他囚犯交流。如果所有囚犯都能找到自己的号码对应的纸条，他们就能成功逃脱。否则他们就都会被囚禁终生。如果每个囚犯都只是随机的打开 $50$ 个盒子，则他们能逃生的概率仅为 ${0.5}^{100}$ ，微乎其微。但是一个聪明的囚犯提出了一个方案：每个人都打开自己的号码对应的盒子，找到下面纸条上的号码，然后打开对应号码的盒子，如此往复，直到找到自己的号码为止。这样做可以显著的将逃生概率增加到 $30\mathrm{\%}$ 左右。 数学上，我们可以把从一个数移动到这个数对应位置的下一个数，如此往复，最终连回自己的结构称为循环（cycle）。比如说 2 3 1就是一个循环，它实际表示了$$ 2\to 3\to 1 \to 2

$$在囚犯问题中，所有号码相当于组成了一个全排列。所有囚犯寻找自己号码的过程就相当于在全排列的各个不同循环中移动一圈。可以证明，一个全排列可以被唯一分解为许多不相交（不共用元素）的循环。 循环的性质：一个有 $n$ 个数的循环可以通过 $n-1$ 次元素交换变回递增的序列。比如循环 2 3 1 就可以通过先交换 $2$ 和 $3$ ，再交换 $3$ 和 $1$ 得到递增序列 1 2 3。 针对数字华容道（$N$-Puzzle）问题，判定是否有解的标准结论如下： 1. **当 $N$ 为奇数时**：盘面有解 $\iff$ 逆序对数（或交换次数）为**偶数**。 2. **当 $N$ 为偶数时**：盘面有解 $\iff$ **（逆序对数 + 空格所在行从下往上的行号）** 为**奇数**。 *（注：这里的行号是从 $1$ 开始计数的，目标状态空格在右下角，即第 $1$ 行）* **重点：** 1. **内存管理**：$N=1000$ 时 $N^2=10^6$。使用 `array.array` 存储 $10^6$ 个整数仅需 4MB，比 `list` 节省约 90% 内存。 2. **输入效率**：$10^7$ 个数字的读取对 Python 来说极具挑战。使用 `itertools.islice` 配合 `map(int, ...)` 是最快的方式。 **优化后的代码：** ```python import sys import array import itertools def solve(): # 1. 使用生成器处理输入，避免一次性加载导致内存超限 def get_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = get_tokens() # 获取测试用例数量 t first_token = next(tokens, None) if first_token is None: return t = int(first_token) # 将标准库函数映射为局部变量，提高循环内的调用速度 write = sys.stdout.write for _ in range(t): n_str = next(tokens, None) if n_str is None: break n = int(n_str) total = n * n # 2. 使用 array.array 节省内存 ('I' 表示无符号 4 字节整数) # 预分配空间比动态 extend 更快 grid_full = array.array('I', map(int, itertools.islice(tokens, total))) # 3. 寻找 0 的位置并计算行号 zero_idx = -1 for i in range(total): if grid_full[i] == 0: zero_idx = i break # 空格所在行（从下往上数，最底下一行是第 1 行） # zero_idx // n 是从上往下数的行索引 (0 ~ n-1) row_from_bottom = n - (zero_idx // n) # 4. 构造不含 0 的紧凑序列用于计算置换环 # 为了极速处理，手动将 0 后的元素前移 grid = array.array('I', [0] * (total - 1)) for i in range(zero_idx): grid[i] = grid_full[i] for i in range(zero_idx + 1, total): grid[i-1] = grid_full[i] # 释放大数组内存 del grid_full # 5. 置换环分解计算交换次数的奇偶性 # 时间复杂度 O(N^2)，对 Python 1s 限制来说 $10^7$ 次操作是极限 num_elements = total - 1 visited = bytearray(num_elements) cycles = 0 # 局部变量优化 g = grid v = visited for i in range(num_elements): if not v[i]: cycles += 1 curr = i while not v[curr]: v[curr] = 1 # 目标状态值 v 在索引 v-1 处 curr = g[curr] - 1 # 交换次数 parity = (总数 - 环数) % 2 swaps_even = (num_elements - cycles) % 2 == 0 # 6. 核心判定逻辑 if n % 2 == 1: # N为奇数：交换次数必须为偶数 write("yes\n" if swaps_even else "no\n") else: # N为偶数：(交换次数 + 空格行号) 必须为奇数 # 逻辑等价于：swaps_even 的布尔值必须与 (row_from_bottom 为奇数) 的布尔值一致 row_odd = (row_from_bottom % 2 == 1) if swaps_even == row_odd: write("yes\n") else: write("no\n") # 显式清理 del grid del v if __name__ == "__main__": solve() ``` **关键点说明：** * **内存（Memory）**：通过 `array.array` 和 `bytearray`，即使在 $N=1000$ 的情况下，核心数据结构占用的内存仅约 5MB。加上 Python 解释器本身的开销，总内存会稳定在 30MB-40MB 左右，远低于 64MB 的限制。 * **时间（Time）**： * 使用 `itertools.islice` 和 `map` 绕过了 Python 慢速的显式 `for` 循环读取。 * 置换环分解通过 `bytearray` 进行标记，时间复杂度为 $O(N^2)$。由于题目保证总元素 $\sum N^2 \leq 10^7$，在 Python 中通过局部变量优化后，可以在 1 秒内完成。 * **偶数阶判定逻辑**： * 目标状态的空格行号是 1（奇数），逆序对是 0（偶数），和为奇数。 * 因此，任何状态只要 `(交换次数 + 从下往上行号)` 的和为奇数，即为有解。 * 代码中的 `if swaps_even == row_odd` 完美涵盖了： * `偶数 + 奇数 = 奇数` (True == True) * `奇数 + 偶数 = 奇数` (False == False) $$