刷题群里有人丢过来一个题目名字叫“HJ143 小红的好排列”。第一反应是得又是小红当工具人。排列题嘛最擅长伪装简单实际上稍不注意就会写一个 n! 的暴力然后看着超时怀疑人生。这个题里的“好排列”在我刷过的常见版本中通常定义成对于长度为 n 的排列 p任意相邻两个位置都满足 |p_i - p_{i1}| ≠ 1。也就是说1 和 2、2 和 3、……、n-1 和 n 这些“差 1 的连号”不能相邻。别小看这个限制它背后是排列计数里一类很经典的“相邻约束”模型。本文准备从暴力枚举、状态压缩 DP一直到包含排斥公式和 O(n) 递推把这个题完整讲一遍。无论你是刚开始刷题的小白还是准备机试想在排列题上拿稳分这篇都值得收藏。1. 题面还原与问题建模1.1 “好排列”到底在限制什么先确定讨论对象。输入一个正整数 n我们有一个 1 到 n 的排列 p (p_1, p_2, ..., p_n)。如果任意 i1 ≤ i n都满足|p_i - p_{i1}| ≠ 1就称这个排列是“好排列”。举两个例子n 4 时排列 (2, 4, 1, 3) 是好的因为相邻差分别为 2、3、2全不是 1。排列 (1, 3, 2, 4) 不好因为 3 和 2 相邻差的绝对值是 1。这个条件看着简单但它不是对某个位置做限制而是对“相邻数字对”做限制。每对数字能否放在一起由它们本身的差值决定。比如 5 和 6 不能相邻但 5 和 7 可以。因为只有 n-1 对“连号”会被禁止所以排列中大多数相邻关系都是合法的。我一开始做这类题也容易犯一个错误只判断相邻两项是否连续却忘记一个数字可能同时和前后两个数字冲突。比如 (2, 1, 3) 里2 和 1 冲突1 和 3 不冲突但整个排列已经不合格了。题目要求每一对相邻都必须满足所以写 check 函数时务必用循环扫完所有相邻位置。1.2 把排列看成图上的“路径选择”排列可以理解为一条经过所有点的路径从 p_1 出发走到 p_2再走到 p_3……每个数字恰好访问一次。那“差 1 的数字不能相邻”相当于什么把 1 到 n 这 n 个点排成一条链链上的边就是1-2, 2-3, 3-4, ..., (n-1)-n一条合法排列就是一条从某个点出发、经过所有点恰好一次的路径并且路径上不能用任何一条链上的边。换句话说每次跳转都必须跳过链上的邻居跳到不相邻的点上。这个“图论视角”非常重要。很多排列计数题表面上在操作数组实际上是在一个图上规划哈密顿路径。一旦转换成图模型包含排斥、动态规划这些工具就能直接用上。后面我们用来推出数学公式的思路也正是基于这个链状图。2. 先写暴力确保你对题目的理解没错2.1 无脑 next_permutation 的写法不管什么排列题第一步永远是暴力。暴力代码写起来快还能帮你验证后续所有优化算法的正确性。C 里直接用next_permutation枚举全排列再写一个 check 函数扫一遍相邻位置。#include bits/stdc.h using namespace std; bool isGood(const vectorint p) { int n (int)p.size(); for (int i 0; i 1 n; i) { if (abs(p[i] - p[i 1]) 1) return false; } return true; } int brute(int n) { vectorint p(n); iota(p.begin(), p.end(), 1); // 生成 1..n int ans 0; do { if (isGood(p)) ans; } while (next_permutation(p.begin(), p.end())); return ans; }next_permutation会按字典序生成所有排列所以不用自己去写回溯。注意iota从 1 开始填充这样排列的数字就是题面上说的 1 到 n。如果输入从 0 开始检查条件就要改成abs(last - nxt) 1之前先加偏移别搞混。暴力时间复杂度是 O(n! × n)。n 8 的时候全排列只有 40320 个跑起来很轻松n 10 就是 360 万个也还行再往上就明显吃力了。所以暴力只用来做数据生成和验证。2.2 用打表结果当作调试基准暴力跑一下前几项得到这张表n好排列数量0111203042514690764685242n 4 的两个好排列分别是 (2, 4, 1, 3) 和 (3, 1, 4, 2)。n 2 和 n 3 时任何排列都会出现差 1 的邻居所以答案是 0。这些数字别小看后面写 DP 和递推全靠它们验证。我建议每个排列题都养成“暴力打表”的习惯。哪怕你准备直接写正解也先把暴力写出来跑出小 n 的结果。后面算法写歪了一对比立刻能发现节省大量调试时间。3. 状态压缩 DP处理 n≤20 的实用解法3.1 状态设计为什么是 mask last暴力枚举的是“下一个数字是谁”在 n 大的时候会爆炸。但是观察题目限制当前能不能放某个数字只取决于上一位置的数字是谁跟更前面的排列没有关系。这种“只关心最后一步”的性质非常适合 DP。既然每个数字只能用一次就需要用一个集合记录哪些数字已经用过了。集合可以用二进制mask表示位数 n第 i 位为 1 表示数字 i 已经被使用。于是 dp 状态可以定义为dp[mask][last] 当前已使用数字集合为 mask且排列最后一个数字是 last 的合法方案数。举个例子mask 的二进制是 0101从低到高表示数字 0 和 2 已经用过此时 last 2说明当前排列是 (0, 2)。要继续放数字只需要检查下一个数字 nxt 是否还没用过同时abs(last - nxt)不等于 1。这个状态为什么够用因为题目限制是“相邻元素差值”跟某个数字之前出现在哪里、排列当前有多长都没关系。唯一和后续决策相关的是已经选了哪些数字、最后一个数字是几。所以 mask last 是一组完备的信息。可以类比成搭积木你现在能不能放下一块只取决于最上面那块的颜色而不是下面整摞积木的排列顺序。3.2 转移方程与初始化初始时排列可以从任意一个数字 i 开始所以dp[1 i][i] 1转移时枚举当前状态 (mask, last)再枚举下一个未使用的数字 nxt。如果abs(last - nxt) ! 1则dp[mask | (1 nxt)][nxt] dp[mask][last]最终所有数字都用完时mask (1 n) - 1答案就是sum(dp[full][last])last 取 0 到 n-1。需要注意答案可能非常大题目如果要求取模就在加法转移时取模。这里用一个通用常量 MOD 1e97实际做题时看题目要求替换。3.3 完整实现和复杂度先看基础版实现int solveDP(int n) { const int MOD 1e9 7; int full (1 n) - 1; vectorvectorint dp(1 n, vectorint(n, 0)); for (int i 0; i n; i) dp[1 i][i] 1; for (int mask 1; mask full; mask) { for (int last 0; last n; last) { int cur dp[mask][last]; if (cur 0) continue; for (int nxt 0; nxt n; nxt) { if (mask (1 nxt)) continue; // 已使用 if (abs(last - nxt) 1) continue; // 差 1非法 int nmask mask | (1 nxt); dp[nmask][nxt] (dp[nmask][nxt] cur) % MOD; } } } int ans 0; for (int last 0; last n; last) { ans dp[full][last]; if (ans MOD) ans - MOD; } return ans; }理论上复杂度 O(2^n × n^2)n 15 完全秒过n 20 大概 4 亿次枚举会有点紧张。实际优化版可以在内层转移时不用遍历所有 nxt而是提前预处理“每个 last 能放哪些数字”的掩码int allow[20]; for (int i 0; i n; i) for (int j 0; j n; j) if (abs(i - j) ! 1) allow[i] | (1 j); // 转移内层 int nxtMask allow[last] ~mask; while (nxtMask) { int nxt __builtin_ctz(nxtMask); // 取出最低位的 1 int nmask mask | (1 nxt); dp[nmask][nxt] (dp[nmask][nxt] cur) % MOD; nxtMask nxtMask - 1; }这样每个状态实际只访问合法候选平均枚举量大幅减少。使用int而不是long long存 dp也能让内存减半。n 20 时dp 数组大小是 2^20 × 20 20,971,520 个 int约 80MB通常还能接受。如果内存卡得很死可以把二维数组压成一维int dp[mask * n last]效果一样。这段代码的输出应该和暴力打表完全一致。我自己写的时候踩过一个坑初始化dp[1 i][i]如果 n 1会有1 0没问题但如果 n 0这个循环不进答案会保持 0而实际空排列算 1 种。所以 n 0 要么单独特判要么初始化时把dp[0][0]设为 1。比赛里通常 n ≥ 1但做模板时还是要注意边界。4. 当 n 变大容斥公式与 O(n) 递推4.1 状态压缩DP的边界在哪状压 DP 的瓶颈是 2^n 的状态数。n 20 时 2^20 ≈ 100 万还能跑n 25 就是 3300 万内存和枚举量都扛不住n 30 基本不可能。如果原题 n 给到了 10^5就必须跳出“枚举集合”的思路去寻找数学结构。这一节我们对“相邻差不为 1”这个问题推导出包含排斥公式再给出一个 O(n) 递推。虽然不同版本的“好排列”定义可能不一样但“用包含排斥统计非法相邻关系”的方法论是通用的。4.2 包含排斥把坏情况精确扣除我们把“数字 i 和 i1 相邻”看成事件 E_i。一个排列是好排列当且仅当所有 E_i 都不发生。直接统计全不发生很难但统计“某些事件一定发生”却比较容易。包含排斥原理就派上了用场。设总共 n-1 个事件E_1, E_2, ..., E_{n-1}。对于任意选出的 k 个事件我们要计算“这 k 个数字对都作为相邻对出现”的排列数。举个例子n 4选出事件 E_11 和 2 相邻要求排列里 1 和 2 必须贴在一起。可以先把 1、2 捆绑成一个块块内部有 (1,2) 和 (2,1) 两种顺序然后把这个块和数字 3、4 一起排列一共 3! 个块的排列再乘以 2得到 12 个。这里块数 n - k 3块内部翻转 2 种。但如果选出的事件有连在一起的比如同时选 E_1 和 E_2要求 1、2 相邻且 2、3 相邻那就意味着 1、2、3 必须组成一个三连块块内部只有 (1,2,3) 和 (3,2,1) 两种顺序块数 n - 2 2所以排列数是 2! × 2 4。这时“翻转因子”不是每个边贡献 2而是每个连续段贡献 2。因此假设选出的 k 条边形成了 r 个连续的“边段”每个边段至少包含一条边。把每个边段连同涉及的顶点捆成一个大块块数为 n - k每个边段内部有两种方向所以包含这 k 个事件的排列数为(n - k)! × 2^r接下来需要统计在一条长度为 n-1 的边链上选 k 条边恰好形成 r 个连续段的方案数。这个组合计数很标准结果是C(k-1, r-1) × C(n-k, r)最后用包含排斥把所有事件组合起来得到A(n) n! Σ_{k1}^{n-1} (-1)^k (n-k)! Σ_{r1}^{k} C(k-1, r-1) C(n-k, r) 2^r这个公式看起来复杂但写代码时只需要预处理组合数 C 和 2 的幂再两层循环累加。用 n 4 验证一下n! 24k1-3! × C(3,1)×2 -36k22! × (44) 16k3-1! × 2 -2总和 24 - 36 16 - 2 2跟打表一致。4.3 简化成 O(n) 递推包含排斥公式虽然漂亮但对每一个 n 都要两重循环n 到 5000 还能接受n 到 10^5 还是慢。针对这道题还有一个更舒服的线性递推A_n (n1) A_{n-1} - (n-2) A_{n-2} - (n-5) A_{n-3} (n-3) A_{n-4}边界条件A_0 1A_1 1A_2 0A_3 0我拿它验证过表里的数据。A_4 5×A_3 - 2×A_2 - (-1)×A_1 1×A_0 0 - 0 1 1 2。A_5 6×A_4 - 3×A_3 - 0×A_2 2×A_1 12 0 0 2 14。和暴力完全一致。写成 C 就是long long solveLinear(int n) { const long long MOD 1000000007; if (n 0) return 1; if (n 1) return 1; if (n 2) return 0; if (n 3) return 0; vectorlong long a(n 1); a[0] 1; a[1] 1; a[2] 0; a[3] 0; for (int i 4; i n; i) { long long v 0; v (v (long long)(i 1) * a[i - 1]) % MOD; v (v - (long long)(i - 2) * a[i - 2] % MOD MOD) % MOD; v (v - (long long)(i - 5) * a[i - 3] % MOD MOD) % MOD; v (v (long long)(i - 3) * a[i - 4]) % MOD; a[i] v; } return a[n]; }这个递推能够直接从包含排斥公式整理得到但我个人更推荐的做法是先用包含排斥公式在较小 n 上算几项再用递推扩展到任意大。这样即使递推系数记错了也能靠暴力打表第一时间发现。实际做题时n 再大也是 O(n)时间和空间都完全可控。5. 常见问题与避坑指南5.1 题目里“好”的定义可能不完全一样这篇文章用的定义是“相邻差值不等于 1”。但我在不同题库里见过“小红的好排列”的其他变体有的要求相邻两个数互质有的要求相邻两个数奇偶性不同也有的直接给出一个坏数集合数字与坏数相邻就不行。遇到题目时第一步一定是读懂题面给出的“好”到底指什么不要先入为主。不同定义下的转移条件不同但 DP 的骨架完全可以复用状态仍是 mask last只是把abs(last - nxt) 1换成对应的判断函数。如果 n 很大状压 DP 用不了那就需要根据新的限制重新找公式或递推。5.2 答案要不要取模以及怎么减排列数增长非常快n 10 时全排列 3628800n 20 时已经是天文数字。题目只要不问“输出方案”大概率要取模。使用包含排斥公式或递推时减法取模特别容易出错。C 里负数取模结果还是负数所以每次减完都要加上 MOD 再取模。我习惯把每一步都写成v (v MOD) % MOD;虽然啰嗦但能避免调试到深夜。5.3 组合数预处理炸了怎么办包含排斥公式里用到组合数 C(n, k)。如果 n 只有几百、几千直接杨辉三角预处理二维数组很稳。n 到 10^5 还非要用公式就要用阶乘和阶乘逆元来算组合数。但注意这道题一旦 n 很大直接用 O(n) 递推更好公式更多是用来辅助推导和验证所以不一定要把阶乘开到极限。5.4 用随机对拍验证一切优化思路写 DP 或递推时我最常做的事就是建一个小型对拍器暴力函数算 n 1 到 8正解函数算同样的 n然后逐一比对。这一步能拦住绝大多数边界错误。递推里系数多一个负号、少一项都会导致结果偏掉状态压缩 DP 里漏掉某个转移也会在某个 n 上鬼使神差地相差 1。有了暴力基准这些错误都能被快速暴露。我在实际做这类排列计数题时最深的体会是不要一上来就背递推公式。公式不是用来背的是用来在暴力打出的序列上做验证的。你先跑出 1, 1, 0, 0, 2, 14, 90 这些数再去套包含排斥和递推心里会踏实很多。另外还有一个对打表特别有用的技巧如果你需要快速生成这个序列的更多项直接用线性递推跑一遍几毫秒就能算出 n 10^6这样你可以随时扩充验证集而不是每次都用暴力去跑 n 12。最后再分享一个细节状态压缩 DP 里的__builtin_ctz在 n 0 时行为未定义但实际 n ≥ 1所以不会有问题。如果编译器是 MSVC没有这个内建函数可以用nxtMask -nxtMask取最低位或者干脆老老实实枚举 0 到 n-1代码可读性反而更高。刷题不是为了炫技稳定通过的代码才是好代码。