P13265 [GCJ 2014 Finals] Power Swapper

在一个平行宇宙里，人们痴迷于使用 $2$ 的幂次方，并且他们为从 $1$ 到 $2^{\mathrm{N}}$ 的数列定义了一种激动人心的排序方式。这里定义的交换操作如下： - 一段可交换的区间是指一个**长度为 $2^{k}$ 的连续区间**，并且其起始位置（从 $0$ 开始计数）必须是 $2^{k}$ 的倍数。 - 一次合法的 $k$ 级交换操作是指交换两个不同的、各自合法的长度为 $2^{k}$ 的区间。 为了将一个给定的排列排序为升序排列，你最多可以对每个 $k \in [0, N)$ 使用一次这样的交换操作。注意，不允许交换一个区间与其自身。 例如，对于排列 $[3,6,1,2,7,8,5,4]$（即 $1$ 到 $2^3=8$ 的一个排列），可以按如下步骤排序： 1. $[3,6,1,2,7,8,5,4]$：执行一次 size-2 的交换，交换区间 $[3,6,1,2]$ 与 $[7,8,5,4]$。 2. $[7,8,5,4,3,6,1,2]$：执行一次 size-0 的交换，交换 $[5]$ 和 $[3]$。 3. $[7,8,3,4,5,6,1,2]$：执行一次 size-1 的交换，交换 $[7,8]$ 与 $[1,2]$。 4. $[1,2,3,4,5,6,7,8]$：排序完成。 上面每一种 size 的交换操作最多只使用了一次。同时，每次交换都满足合法性：两个长度为 $2^k$ 的区间起始位置均为 $2^k$ 的倍数。 现在请你计算，将给定排列按上述规则排序，有多少种不同的方式？每一种方式是一个有序的交换序列，只有当两种方式的交换序列完全一致时，才认为它们相同。

输入的第一行是测试用例数 $\mathrm{T}$。接下来是 $\mathrm{T}$ 个测试用例。 每个测试用例的第一行是一个整数 $\mathrm{N}$，表示排列的大小为 $2^{\mathrm{N}}$。 下一行是 $2^{\mathrm{N}}$ 个用空格分隔的整数，表示一个 $1$ 到 $2^{\mathrm{N}}$ 的排列。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是将给定排列按题目要求排序的不同方法数。

## 限制条件 - $1 \leq \mathrm{T} \leq 200$ ### Small 数据集（4 分） - 时间限制：~~60~~ 3 秒 - $1 \leq \mathrm{N} \leq 4$ ### Large 数据集（12 分） - 时间限制：~~120~~ 5 秒 - $1 \leq \mathrm{N} \leq 12$ 翻译由 ChatGPT-4o 完成