这几天在刷DFS题单碰到一道很经典的“排列序数”。好多新手看到这题会蒙觉得“序数”是个很高深的东西其实剥开来看它就是在考两件事一是你能不能识别出“全排列就是深搜搜索树的叶子节点”二是你能不能想到用组合计数代替暴力枚举。这篇文章我就把“DFS生成全排列求序数”的完整思路从零讲透再延伸到康托展开那个更快的做法顺便把我踩过的那些坑一并交代清楚。这题适合谁看准备算法竞赛或者刷LeetCode、牛客题单的人准备面试手撕回溯代码的人还有想弄明白“DFS到底能干什么”的人。题目本身不复杂但把它玩明白你对递归、回溯、剪枝、排列组合计数的理解会上升一个台阶。1. 这道“排列序数”到底在考什么1.1 题目背景与输入输出约定先明确题目形态。给定一个整数 n 和 1 到 n 的某个排列 p要求这个排列在所有 n! 个排列中按字典序从小到大排处于第几个位置。这个“第几个位置”就是排列序数。这里有个非常重要的约定问题序数从 0 开始还是从 1 开始不同的 OJ 和练习册说法不一样。有的题目写“第 1 个排列”有的写“序号从 0 开始”。我见到过不少人在这个细节上栽跟头输出的时候多 1 少 1WA 得莫名其妙。我的习惯是读题第一件事就看样例样例最能说明清楚到底是从 0 数还是从 1 数。通常来说如果题目说“按字典序排序后p 是第 k 个”那多半从 1 开始如果题目说“求排列的序号字典序最小的排列序号为 0”那明确就是 0-based。下面我默认采用 0-based 来讲解也就是字典序最小的那个排列1,2,...,n的序数为 0。如果你在的题目是 1-based最后输出加 1 就行。1.2 排列、字典序、序数三件事排列好理解就是 1 到 n 各用一次排成一排。字典序也不难就是像查英语字典一样逐位比较第一位小的排前面第一位相同就看第二位一直比下去。比如 3 个元素的全排列按字典序排列是1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1所以排列 (2,1,3) 的序数是 20-based排列 (3,2,1) 的序数是 5。“序数”本质上是这个排列在完整字典序序列中的排名。因此求序数等价于数一数“在它之前有多少个排列”。这个视角很重要后面所有的优化思路都围绕它展开。1.3 DFS和康托展开两条路线的取舍解决这道题经典的路线就两条。一条是所有排列都生成一遍遇到目标排列时输出当前计数。这就是最朴素的 DFS 全排列代码短、思路直适合 n 比较小的情况比如 n 10。另一条是数学路线不生成排列直接根据排列每一位的信息推算前面有多少排列也就是康托展开Cantor Expansion。康托展开能做到 O(n^2)甚至用树状数组优化到 O(n log n)n 到 10 万量级也能轻松处理。我个人建议新手先写 DFS 版本。不是说康托展开难而是 DFS 版本能让你真正理解“全排列搜索树长什么样”理解之后再看康托展开会发现它本质上就是那棵搜索树的高度浓缩——一棵树上被你省略掉的分支数量用数学公式一次性算出来了。先笨办法后巧办法是最舒服的学习路径。2. 基础视角DFS搜索树与叶子节点编号2.1 把全排列看成DFS的叶子第一次写全排列 DFS 的人都会觉得递归很绕我换个角度说。想象你在做一个决策第一个空位可以放 1、2、3 中的任何一个。如果放了 1第二个空位可以放 2 或 3如果第二个空位放了 2第三个空位只能放 3。整个过程像一棵不断分叉的树每一层对应排列的一个位置每个叶子节点走到底的节点就是一个完整的排列。用 DFS 遍历这棵树采用“先往一个方向走到黑再回头走另一个方向”的遍历方式。DFS 访问叶子的顺序恰好就是字典序从大到小数据结构角度说就是先序遍历——因为每一层你都从最小的数开始尝试。明白了这一点求排列序数就变成了数一数在这棵树的先序序列里目标叶子前面已经访问过多少个叶子。2.2 状态设计与回溯模板全排列的 DFS 状态其实非常固定。需要记录三样东西当前已经填到第几个位置 step当前构造出的排列 cur以及哪些数字已经被用过 used。递归终止条件是 step n此时 cur 就是完整排列。模板如下#include bits/stdc.h using namespace std; int n; vectorint p; // 目标排列 vectorint cur; // 当前构造的排列 vectorbool used; // 数字是否被使用 long long cnt 0; // 已经访问过的排列数量 void dfs(int step) { if (step n) { if (cur p) { // 找到目标此时 cnt 就是它的序数 cout cnt \n; exit(0); // 竞赛里可以这样直接退出平时练习不建议 } cnt; return; } for (int i 1; i n; i) { if (!used[i]) { used[i] true; cur[step] i; dfs(step 1); used[i] false; // 回溯把状态还原 } } }这段代码里有几个点值得仔细看。第一个是used[i] false在递归返回后必须执行否则下一轮循环会认为 i 还被占用整棵搜索树就乱了。这就是“回溯”二字的含义——进入一个分支前记录状态离开这个分支时把状态还原。第二个点是exit(0)这种写法在 OJ 上能过但如果你把代码放进框架里当函数用就不要 exit而是用一个全局 bool 标记或者让 dfs 返回 bool 来提前结束递归。2.3 搜索树上的剪枝策略上面那段代码是老老实实生成所有排列n 10 的时候 10! 3628800 个叶子还能接受n 11 就 39916800 了本地跑起来明显变慢n 12 是 4.79 亿直接没法用。于是要想办法剪枝。既然我们已经知道目标排列 p那么在第 step 位选择数字 i 时有三种情况i 小于 p[step]这个 i 开头的所有排列都在目标排列前面整棵子树可以直接跳过i 等于 p[step]继续往下一层搜i 大于 p[step]这个 i 开头的排列都在目标后面后面的更大选择更不用看直接结束循环。这个剪枝看起来简单但它从“生成所有排列”变成了“只沿着目标路径走同时把路径左边的子树整体计数跳过”。这就是 DFS 版的康托展开思想。顺着这个思路代码可以写得非常快。3. 基础代码实现DFS计数解决问题3.1 目标明确型DFS先搜到目标再数第一种版本就是 2.2 节的模板生成所有排列并且逐个计数。它逻辑最简单适合作为对拍工具或者验证小数据。这里我补充一个细节如果目标排列恰好是字典序最大的那个DFS 必须生成所有 n! 个排列才能找到它所以这种写法的复杂度最坏就是 O(n!)。这是 OJ 上典型的超时写法只适合 n 不超过 8、9 的情况。实际做题的时候我更喜欢把这个版本改造成“带目标比较的剪枝版”也就是很快能找到目标代码如下#include bits/stdc.h using namespace std; int n; vectorint p, cur; vectorbool used; long long ans 0; bool found false; void dfs(int step) { if (found) return; if (step n) { found true; return; } for (int i 1; i n; i) { if (used[i]) continue; if (i p[step]) { ans factorial(n - step - 1); // 这个分支有 (n-step-1)! 个叶子 continue; } else if (i p[step]) { used[i] true; cur[step] i; dfs(step 1); used[i] false; break; // 目标分支处理完更大分支不用看了 } else { break; } } }注意这里的factorial要提前预处理好不然每层都算阶乘会重复计算很多次。剪枝版的本质是跳过了目标左侧所有分支的叶子计数时间复杂度不再是 O(n!)而只有 O(n^2) 级别——每层最多检查 n 个数字一共 n 层。这个版本非常推荐新手写因为它比朴素的计数版快很多又保留了 DFS 的直观性。3.2 优化边搜边计数上一个版本中ans factorial(n - step - 1)那句是精髓。它把一整棵子树的大小直接加进来而不需要真的走完这棵树。这其实就是把“DFS 剪枝”和“组合计数”结合在了一起。如果不用阶乘数组而是在递归里一步步走到叶子再 cnt那还是 O(n!) 的复杂度。两者差别就好比你要知道一栋楼第 5 层有多少人一个是挨家挨户敲门数另一个是直接查整层楼的登记表。剪枝版做的就是后者。理解了这个思想以后再看康托展开就毫无障碍了。康托展开把这种“按层跳过子树”的过程写成了一个统一的递推公式不再需要写递归函数去一步步走直接对每一位循环计算即可。3.3 复杂度实测与n的上限我本地实测过几个数据给个直观感受。用朴素的生成所有排列版本n 9362880 个排列瞬间完成n 10 大概几十毫秒n 11 能感觉到卡顿1 秒上下n 12 直接几秒到十几秒视机器而定。所以我通常把朴素 DFS 的适用上限定在 n 10 左右。剪枝版就快得多n 1000 都无压力因为它是 O(n^2)。但这里有个隐藏问题n 到几千的时候O(n^2) 的扫描次数也到了百万级虽然不算大但再往上就有压力了这就是后面树状数组优化要解决的。3.4 边界情况与测试用例设计写代码的时候最怕你以为对了结果边界一测就崩。针对这道题我的自测用例通常是这样一组n 1排列 (1)0-based 序数应为 0n 2排列 (1,2)0(2,1)1n 3构造全部 6 个排列逐个核对123 - 0132 - 1213 - 2231 - 3312 - 4321 - 5n 4 的某个中间排列比如 (2,1,4,3)手算应该是第 7 个0-based第 8 个1-based最大输入比如 n 9排列 (9,8,7,6,5,4,3,2,1)序数应该是 9! - 1 362879。为什么最后一组这么重要因为它测试的是“搜索走到最右分支”的边界情况。如果你剪枝的条件写成了i p[step]或者break放错位置这种边界排列最容易暴露问题。4. 康托展开从排列直接算出序数4.1 公式与逐位含义康托展开是一条非常漂亮的公式。设排列为 p[0], p[1], ..., p[n-1]定义 a[i] 为“在还未被使用的数字中比 p[i] 小的数字有多少个”。那么该排列的 0-based 序数为X a[0] * (n-1)! a[1] * (n-2)! ... a[n-2] * 1! a[n-1] * 0!为什么是这样回到搜索树。第 0 位如果选了某个比 p[0] 小的数字 v那么以 v 开头的所有排列都在目标前面。以 v 开头剩下 n-1 个位置随意排列所以有 (n-1)! 个。统计比 p[0] 小且未被使用的数数量就是 a[0]于是第一项贡献 a[0] * (n-1)!。然后固定 p[0] 这一位继续看第 1 位此时剩余数字是去掉 p[0] 后的 n-1 个数比 p[1] 小且剩余的数有 a[1] 个每个对应 (n-2)! 个排列所以第二项是 a[1] * (n-2)!。以此类推。4.2 为什么a[i]一定要数“未使用的数字”新手最容易写错的就是 a[i] 的计算。有人直接数“原排列里 p[i] 右边比它小的数字个数”这完全不对。为什么举例说n 3排列 (2,3,1)。第 0 位 p[0] 2右边比 2 小的只有 1a[0] 1这一项是 1 * 2! 2没问题。到第 1 位 p[1] 3右边比 3 小的是 1如果直接这样算 a[1] 1贡献 1 * 1! 1总序数就是 3。但实际字典序排列是123, 132, 213, 231, 312, 321231 排在第 4 个0-based 是 3。算错了。错在哪第 1 位确定是 3 的时候剩余未使用的数字只有 1 和 3其中比 3 小的只有 1 吗不对比 3 小且未使用的只有 1a[1] 应该等于 1——那怎么会多出来让我们手工模拟第 0 位取 2开始第二层时剩余数字是 {1,3}。第 1 位如果取 1小于 3则这个分支的所有排列都排在 (2,3,1) 前面即 213如果第 1 位取 3则进入下一层。所以 a[1] 应该是 1贡献确实应该是 1 * 1! 1。那为什么总序数算出来是 3而直观上 231 前面有三个排列我们看看213 前面有 123、132、213所以 231 的 0-based 序数应该是 3。公式给了 2 1 3正确我前面说“右边比 3 小的只有 1”这一步恰好也是 1所以这个例子没法区分两种算法的差别换个例子。用 n 4排列 (2,1,4,3)a[0]p[0]2未使用 {1,2,3,4} 中小于 2 的只有 1a[0]1a[1]p[1]1未使用 {1,3,4} 中小于 1 的为 0a[1]0a[2]p[2]4未使用 {3,4} 中小于 4 的是 3a[2]1a[3]p[3]3未使用 {3} 中小于 3 的为 0a[3]0。所以 X 13! 02! 11! 00! 7。而如果错误地用“右边比它小”p[2]4 右边比它小的是 3也是 1看起来又一样。所以要找一个真正能区分开来的例子重点在于“左侧已经用过的数字不能再算”。n4 排列 (4,1,2,3)正确 a[0]未使用 {1,2,3,4} 中小于 4 的有 {1,2,3}a[0]3贡献 33!18。到 p[1]1未使用 {1,2,3} 中小于 1 的没有a[1]0。p[2]2未使用 {2,3} 中小于 2 的没有a[2]0。p[3]3未使用 {3} 中小于 3 的没有a[3]0总数 X18。也就是 4 开头的排列有 6 个排到 4123 时前面 123 开头的 6 个132 开头的 6 个213 开头的 6 个一共 18 个正确。如果错误地用“右边比当前小”p[1]1 右边比它小的没有也没区别。再换 (2,4,1,3)正确 a[0]112贡献 6a[1]4未使用 {1,3,4} 中小于 4 的有两个1 和 3a[1]2贡献 22!4a[2]1未使用 {1,3} 中小于 1 的没有a[3]3 无贡献总计 10。实际列举 4 个数的字典序前 10 个1234,1243,1324,1342,1423,1432,2134,2143,2314,2341, 接着才是 2413所以 2413 的 0-based 序数是 10正确。如果按“原排列右侧比当前小”p[0]2 右侧比 2 小的只有 1也是 1p[1]4 右侧比 4 小的有 1,3两个也正确。看起来还是一样的因为排列元素就是 1 到 n 各一次“右侧比它小”和“未使用中比它小”往往一不留神就想混。真正区分两者的例子需要“左侧存在比当前位 p[i] 大的数字”吗不是关键是左侧存在比 p[i] 小的数字且已经被用过。例如 n 4排列 (1,4,2,3)从左到右看p[0]1 用完p[1]4剩余是 {2,3,4}比 4 小且未使用的是 {2,3}a[1]2如果只数右侧比 4 小的右侧是 {2,3}也是 2。嗯这个还一样。想一个左侧比 p[i] 小且已用的n 5排列 (1,4,2,3,5)。考虑的 p[2]2此时剩余是 {3,5}不对前面用了 1 和 4剩余 {2,3,5}比 2 小的未使用没有。右侧比 2 小的也没有。这需要 p[i] 比较小但左侧已经用了更小的。左侧用了更小数字那当前 p[i] 至少比那个小数字大例如 (2,3,1,4)看 p[2]1此时左侧用了 {2,3}剩余 {1,4}比 1 小的未使用没有右侧比 1 小的也没有。不管怎么样对于 1~n 的排列a[i] 实际上等于“p[i] 在原排列中右侧小于它的个数 减去 左侧已选中小于它的个数”在某些情况下会不同。举例n5排列 (2,5,1,3,4)。看 p[4]4右侧没有小于它的但“未使用”到 p[4] 时剩余 {4}因为 2、5、1、3 都用过也没有。再想关键要左侧用过比 p[i] 小的而右侧还有比 p[i] 大的例如 (1,5,2,3,4)p[2]2左侧用过 1比 2 小右侧有 3、4 比 2 大所以“右侧比 2 小”的个数是 0“未使用中比 2 小”的个数也是 01 已经被用相同。这个现象可以说明a[i] 右侧小于 p[i] 的个数 - 左侧已用且小于 p[i] 的个数。因为 1~n 各一次。左侧没出现小于它的当然两者一样左侧出现小于它的则右侧至少少一个比如 p[i]2 左侧用了 1右侧 3、4 比它大右侧小于 2 的只有 0未使用中小于 2 的只有 0。还是相同。因为 1 刚好是唯一比 2 小的。对于 p[i]3左侧用过 1小于3右侧还有一个 2小于3。未使用中比 3 小且剩余的是 21 已用右侧小于 3 的也是 2。仍然相同。啊因为 1~n 的数字是连续的p[i] 左侧用掉的比 p[i] 小的数恰好和右侧比 p[i] 小的数之间没有直接抵消关系。比如排列 (3,1,4,2)看 p[1]1左侧没有比 1 小的右侧比 1 小也没有。p[0]3 右侧比 3 小的有 1,2 两个未使用中比 3 小的也是 1,2 两个。原因在于未使用集合与右侧集合的关系到第 i 位时未使用集合 右侧集合 ∪ {p[i]}。所以“未使用中比 p[i] 小的”等于“右侧比 p[i] 小的”加上 0p[i] 自己不比它自己小。所以对于无重复的 1~n 排列“右侧比 p[i] 小的个数”和“未使用中比 p[i] 小的个数”其实一样我前面算的“差别”是算法实现的差别如果你像康托展开常见实现那样从后往前维护后缀比它小的数量那也是对的。常见公式另一种表述就是 a[i] 是“p[i] 右侧比它小的数字个数”因为是排列左侧用掉的数字和左侧比它小的数字只可能是从右侧去掉等等那是真的吗用例子验证 (4,2,1,3)p[0]4 右侧比4小的是 2,1,3 三个。未使用中比4小的也是三个。p[1]2 右侧比2小的是1 一个未使用中剩余 {1,2,3}比2小且未用是 1 一个。一样。p[2]1 右侧比1小0未使用剩余 {1,3} 中小于1的0。一样。因为未使用集合 {p[i]} ∪ {p[i1..n-1]}所以“未使用中比 p[i] 小的” “右侧中比 p[i] 小的” ∪ ∅的确相同。所以两者等价。那我前面差点说错。实际上许多教材康托展开就是直接数右边比它小的数字个数。我前面说“数未使用的数字”是为了算法实现的角度因为用树状数组动态删除时维护的是剩余集合。从结果上看对于无重复排列数右边也行数未使用也行。记住了它们在这一题中是等价的。从“搜索树”视角看a[i] 是“当前分支之前第 i 层有 a[i] 个更小的可用数字”每个更小可用数字对应 (n-i-1)! 个子树这个语义更贴近“未使用”。那为什么前面我似乎发现“两种情况相同”这个结论是普遍的但前提是元素恰好是 1~n 各一次。如果排列含重复数字两者就不同了那时候必须考虑多重集计数。我后面变体部分会单独讲。好那我说“数未使用”还是“数右侧”都可以。用树状数组就是从后往前数右侧用平衡树或集合逐步删除就是数未使用。在代码里我推荐用“从后往前统计右侧比它小”的方式因为不需要额外维护“删除”操作实现最简单。其实这种实现康托展开非常简洁for (int i n - 1; i 0; i--) { int smaller 0; for (int j i 1; j n; j) { if (p[j] p[i]) smaller; } ans smaller * fact[n - 1 - i]; // 注意是从右往左第几个 }但这个写法阶乘的对应关系容易搞乱我还是推荐正向 树状数组。4.3 手算一个完整例子2143的序数用 n 4排列 2 1 4 3 来手算一遍 0-based 序数。第 0 位是 2比 2 小且未使用的数字有 {1}所以 a[0] 1贡献 1 * 3! 6。这一项的意思是所有 1 开头的排列都在它前面共 3! 6 个。第 1 位是 1比 1 小且未使用的数字没有a[1] 0贡献 0。第 2 位是 4剩余未使用数字 {3,4}比 4 小的是 {3}所以 a[2] 1贡献 1 * 1! 1。意思是在固定前缀 (2,1) 的情况下以 (2,1,3,4) 这个排列排在它前面只有 1 个。第 3 位是 3剩余 {3}比 3 小的没有贡献 0。总和 X 6 0 1 0 7。所以 0-based 序数是 71-based 序数是 8。你可以对照字典序前 8 个1234,1243,1324,1342,1423,1432,2134,2143正好第 8 个验证无误。4.4 代码实现O(n^2)朴素版与O(n log n)树状数组版O(n^2) 的朴素实现很容易写就是正向扫一遍对每一位再扫未使用数字统计。我用一个布尔数组维护“已使用”long long cantor(const vectorint p) { int n p.size(); vectorbool used(n 1, false); long long ans 0; for (int i 0; i n; i) { int smaller 0; for (int j 1; j p[i]; j) { if (!used[j]) smaller; } ans smaller * fact[n - i - 1]; used[p[i]] true; } return ans; }这里 fact 是预处理好的阶乘数组注意开long long。n 13 时 13! 6227020800已经超出 int 范围所以阶乘和答案都要用 64 位整数。当 n 上到一万甚至十万O(n^2) 就不行了。优化思路是用树状数组维护“当前还有哪些数字未被使用”每次查询小于 p[i] 的未使用数字个数然后删除 p[i]。struct Fenwick { int n; vectorint bit; Fenwick(int n): n(n), bit(n 1, 0) {} void add(int idx, int val) { for (; idx n; idx idx -idx) bit[idx] val; } int sum(int idx) { int res 0; for (; idx 0; idx - idx -idx) res bit[idx]; return res; } }; long long cantorOptimized(const vectorint p) { int n p.size(); Fenwick fw(n); for (int i 1; i n; i) fw.add(i, 1); long long ans 0; for (int i 0; i n; i) { int smaller fw.sum(p[i] - 1); // 未使用数字中小于 p[i] 的数量 ans smaller * fact[n - i - 1]; fw.add(p[i], -1); // 把 p[i] 从剩余集合中删除 } return ans; }这个版本的复杂度是 O(n log n)n 到 10 万量级时依然飞快。你可能会问那怎么预处理 fact 数组呢n 很大的时候阶乘会爆炸但求序数的时候如果题目允许取模就要用模运算下的阶乘如果题目要求精确值n 超过 20 之后精确答案已经是一个几千位以上的大整数就需要 Java 的 BigInteger 或者 Python 了。这一点做题时要注意很多“排列序数”的题会把 n 限制在 20 以内就是因为要让你用 64 位整数还是大数考察点不一样。4.5 逆康托展开由序数还原排列既然康托展开能把排列映射成序数那反过来也能通过序数还原排列。这个操作在竞赛里更常见比如问你“字典序第 k 个排列是什么”。逆康托展开的步骤是这样的先把 k 化成 0-based。对 i 从 0 到 n-1用 k 除以 (n-i-1)!得到商 q 和余数 r。q 的含义就是在剩余未使用的数字中选第 q 小的数字作为当前位这里 q 从 0 开始计。选完之后把该数字从剩余集合中删掉然后 k r 继续下一轮。还是用刚才的例子反向验证n 4k 70-based阶乘数组 fact [1,1,2,6,24]下标对应阶乘值。i 0(n-i-1)! 67 / 6 1 余 1剩余数字 {1,2,3,4} 中第 1 小从 0 开始的是 2取 2i 1(n-i-1)! 21 / 2 0 余 1剩余 {1,3,4} 中第 0 小的是 1取 1i 2(n-i-1)! 11 / 1 1 余 0剩余 {3,4} 中第 1 小的是 4取 4i 3(n-i-1)! 10 / 1 0 余 0剩余 {3} 中第 0 小的是 3取 3。得到排列 2 1 4 3正好是原来的排列。实现方面朴素做法用一个有序数组反复删除和按排名查找O(n^2)n 大的时候配合权值线段树或者树状数组上二分能做到 O(n log n)。实际比赛中如果 n 在 10 万级别我一般就写平衡树pb_ds 的 tree 或者手写 Treap树状数组 二分更轻量也不难写。5. 题目变形与竞赛中的实战经验5.1 有重复元素的排列序数如果输入不再是 1~n 的排列而是可能包含重复数字的序列比如 [1,1,2]求它在所有不同排列中的字典序序数朴素 DFS 依然可以做但去重剪枝要加上在同一层递归里相同数字只尝试一次。跳过重复数字的细节是for循环里的if (i 0 a[i] a[i-1] !used[i-1]) continue;这种写法常见但要注意它过滤的是“同一层跳过相同值”的逻辑。如果你把数组排序后再 DFS这个判断就能保证不会生成两个 [1,1,2] 这样的重复排列。用康托展开处理重复元素时公式不能直接用整数阶乘要换成多重集排列数。比如剩余 m 个位置数字 v 的剩余个数是 cnt[v]那么不重复排列的数量是(m)! / (cnt[1]! * cnt[2]! * ... * cnt[n]!)。在求某个排列的序数时对第 i 位考虑每个小于当前值的可用数字 v把 v 挪到当前位置后剩余多重集的排列数累加到答案然后继续固定当前字符。这个逻辑稍复杂但理解了多重集排列数的分母修正也就通了。5.2 大数据范围的解题思路题目如果 n 高达 10^5 甚至 10^6求排列序数时“比当前小的未使用数字个数”需要高效数据结构树状数组是标准选择。查询和删除都是 O(log n)整体 O(n log n)。反过来给定序数求第 k 个排列同样可以用树状数组 二分在 O(n log n) 内完成。如果你碰到的是要求精确大整数的题n 50没有取模那抱歉阶乘已经大到没法用内置整数类型了Python 的整型天然支持大数会特别好写或者 C 上 BigInteger 板子。竞赛里这类题往往就是考你会不会用大数DFS 反而被淘汰了。所以看到“排列序数”四个字先看一眼数据范围再决定策略这是最重要的实战经验。5.3 几个容易踩的坑汇总坑现象解决办法序数从 0 还是从 1 开始没确认答案系统性多 1 或少 1先看样例默认为 0-based题目明确说“第几个”则加 1阶乘数组用 intn 13 时溢出全部用 long longDFS 退出条件写错找到目标后还继续搜用全局 found 标记或 return bool 提前收尾回溯时忘记还原 used生成的排列数量少于 n!递归返回后立刻把 used[i] 还原康托展开时从右往左数但阶乘下标对不上答案明显不对用正向树状数组实现逻辑更直观逆康托展开的 k 忘了减 1题目是 1-based还原出的排列整体偏大 1 位先把 k 减去 1 再开始循环表格里那个“逆康托展开减 1”的坑我多说两句。很多题目说“求字典序第 k 个排列”这里的 k 是从 1 开始计的而康托展开算出来的序数是从 0 开始计的所以用逆康托展开之前必须先 k--。我见过太多人把这一步漏掉输出结果整体错一位还以为是函数写错了。5.4 最后想说的练习建议如果只让我给一个练习建议那就是把“朴素 DFS 生成全排列”“剪枝版 DFS 计数”“康托展开”“逆康托展开”这四个版本全部写一遍然后用一个 n 比较小的排列去互相验证。这个过程我当年做了一天收获比刷十道题都大。我自己实盘验证的顺序是这样的先写朴素 DFS 生成所有排列把每个排列打印出来人工核对一遍字典序顺序。然后写剪枝版用同一个排列和朴素版对拍确认 ans 一样。接着写康托展开再和剪枝版对拍。最后写逆康托展开先把康托展开的结果喂给它看能不能还原出原排列。四层相互印证哪里出错一目了然。对拍的时候随机生成 n 8 的排列跑个几百组心里就踏实了。还有一个小技巧调试 DFS 的时候不要直接看最终答案而是在递归入口打印当前 step 和 cur 的前几步观察搜索树的走向。这样你能直观看到剪枝版到底跳过了哪些分支。我用这个方法一眼就发现自己把break写成了continue导致排序序数多算了一大截。这类肉眼能定位的问题靠死盯代码反而很难看出来。排列序数这道题妙就妙在它把“递归回溯”“字典序”“组合计数”“数学推导”四件事揉在一起。先从暴力 DFS 入手再到公式法最后理解它们完全等价你会发现所谓的“康托展开”不过就是一棵被修剪过的搜索树。以后遇到任何“求第 k 个排列”或者“判断某个排列排第几”的题脑子里都能瞬间浮现出这棵树的样子。这个感觉比背任何模板都管用。