当年在考场上第一次看到“火星人”这道题心里又惊又喜。惊的是题面很有意思外星人用手指数数每个手指还都有自己的编号喜的是它本质上就是全排列字典序的下一个排列这不就是当年教科书上“求后继排列”的经典问题吗结果真动手写的时候我卡了挺久。因为N和M都可以到10000直接傻乎乎地从第一个排列开始枚举到目标位置根本不可能而如果只会用DFS全排列去“数”N一大早就爆了。这篇文章就从洛谷P1088这道题出发把“给定一个排列求它后面第M个字典序排列”这件事彻底讲清楚。既有考场上一行STL带走的偷懒做法也有原理层面的排列序号进位法。不管你是备战NOIP、CSP-J/S的选手还是刚学全排列、康托展开的初学者都能找到自己能用的东西。1. 题目解读与核心难点1.1 火星人的手指密码到底是什么先还原一下题面火星人有一排N根手指每根手指都有一个不重复的编号从1到N。他们计数的方式很特别把手指从左到右排成一列用一个排列来表示一个数。所有的排列按照字典序从小到大排列好比如N3的时候就是123、132、213、231、312、321这样一路排下去。外星人会先伸出某个排列然后告诉你“我要继续往后数M个数”你要算出他最后摆出来的那个排列是什么。输入给的是N、M以及当前伸出的那个排列。N和M的范围都是10000以内。也就是说N10000、M10000是可能出现的而且题目只给一个测试点时限一般是1秒左右。这不是一道让你去脑补“外星人有多神奇”的题它考的就是排列生成、字典序以及如何处理大规模数据。1.2 为什么不能直接从第一个排列开始数很多新手第一反应是既然所有排列已经按字典序排好了那我用搜索把从123...N开始的排列一个一个生成出来数到目标位置不就行了这个思路在N很小的时候完全成立。N3、N4的时候DFS把全排列枚举出来再从头找目标排列的下M个完全没问题。但问题是N最大到10000。全排列的个数是N!这个数字增长得极其恐怖N10就已经300多万个N10000根本不可能一一枚举。所以这道题考查的重点不是“生成全排列再查找”而是“已知一个排列如何在这个有序的排列序列中向后跳跃M步”。换个更简单的说法123和132是两个相邻的排列但要你直接从“87654321”这种排列往后跳10000步总不能把它前面几十亿个排列全扫一遍吧我们需要的是排列与排列之间的“加减法”运算而不是把所有排列都暴力列出来。1.3 数据范围直接决定思路走向看到N、M都是10000其实是在暗示你可以接受O(NM)级别的解法也可以接受O(N log N)级别的解法但绝对不能接受O(N!)或者O(2^N)之类的东西。换句话说这道题给了两条路一条路是利用STL的next_permutation函数每次在当前排列上向后走一步重复M次。由于next_permutation的单次平均代价很低实际运行往往跑不满O(NM)很多选手用这个写法直接AC。另一条路是把排列看成一个奇特的“数字”通过进制进位的思想直接从原排列加上M得到新排列。这个写起来复杂一点但时间复杂度是稳定的O(N log N)。我当年在考场上先用了第一种方法AC之后又回头研究第二种发现它对于理解康托展开、逆康托展开非常有帮助。下面两章分别展开讲。2. 思路ASTL next_permutation 通关最简单写法2.1 next_permutation 到底做了什么C的STL里有一个函数叫next_permutation它做的事情就是对于一个数组表示的排列原地修改它使它变成字典序中的下一个排列。如果当前排列已经是字典序中最大的那个比如N3时的321函数会返回false并把数组改成最小的排列123。它的原理其实只有三步从后往前找到第一个满足a[i] a[i1]的位置i这个位置就是需要变动的“关键位置”。如果整个数组从后往前一直是降序说明已经不存在更大的排列。再从后往前找到第一个比a[i]大的元素a[j]。交换a[i]和a[j]然后把i1到末尾这一段反转。因为这段原本是降序反转后变成升序刚好得到字典序中紧挨着的下一个排列。举个例子123的下一个排列是132。从后往前看2 3所以i指向2这个位置然后从后往前找第一个比2大的数找到3交换得到132然后i1到末尾只有一位不用反转完成。整个next_permutation的时间复杂度最坏是O(N)但平均情况下只需要扫描尾部一小段。比如从123456到123465只需要改动最后两位。这也是为什么很多人说“M次调用也能过”的根本原因。2.2 考场上一行STL带走的代码对于P1088代码短到令人感动#include bits/stdc.h using namespace std; int n, m; int a[10005]; int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%d, a[i]); } while (m--) { next_permutation(a 1, a n 1); } for (int i 1; i n; i) { printf(%d , a[i]); } printf(\n); return 0; }注意next_permutation接收的是迭代器区间左闭右开。数组从1开始存储时就是a1到an1。如果谁把右边界写成an那永远只会对前n-1个元素做排列最后一个元素始终不变提交上去等着Wrong Answer吧。我在这里要提一句如果你使用的是vector对应的写法是next_permutation(v.begin(), v.end())不需要加1因为vector迭代器是从0开始的。别在vector、数组混用的时候搞混。2.3 复杂度、风险与考场上怎么选这个写法的时间复杂度理论上限是O(NM)也就是1e8。有不少人拿到OJ上一跑几百毫秒就过了越觉得玄学。其实next_permutation每次调用都要从后往前找第一个上升点。如果排列尾部比较随机大多数情况下上升点很快就能找到扫描长度很短。只有在排列呈整体降序、接近末尾的时候单次扫描才会接近O(N)。所以实际运行时间远远好于最坏情况。不过OI比赛里“实际跑得快”和“理论上说得过去”是两回事。我见过一些选手因为依赖STL而翻车不是这道题翻车而是遇到某些数据恰好卡在next_permutation的坏情况下导致超时。所以我的建议是如果你现在打的是普及组、CSP-J这类比赛N、M在10000以内用next_permutation完全可行不要有心理负担。如果你想扎实掌握排列算法或者担心以后遇到N、M更大的变种题那就一定要会下一章的手写进位法。STL虽好但背后的原理才是通用能力。3. 思路B排列序号进位法原理更优的解法3.1 排列也可以当成一个“数字”来算如果说next_permutation是“一步一步走”那进位法就是“坐电梯直达目标层”。要理解它先得明白一个很漂亮的性质任何一个排列都能唯一转换成一个“变进制数”。这个变进制数每一位表示的含义是当前这个位置上右边剩下没有用过的数字中有多少个比它小。举个N3的例子看排列231第一位是2。在还没用过的数字{1,2,3}中比2小的只有1所以这一位对应的系数是1。第二位是3。此时还剩下{1,3}比3小的只有1所以这一位系数也是1。第三位是1。此时剩{1}比1小的一个都没有系数为0。所以231对应的系数序列是(1,1,0)。这个系数序列从左到右乘以(n-1)!、(n-2)!、...、0!再累加起来就是这个排列在字典序中的编号。计算一下1×2! 1×1! 0×0! 3。也就是说在字典序从0开始编号的情况下231确实是第3个排列。你可以对照一下0号是1231号是1322号是2133号正好是231完全吻合。这就是经典的康托展开。很多教材上是直接给公式初学者看得一脸懵。我自己当年学的时候是把它想象成“按位确定排列”的编号第一位有N种选择其中第x小的数字就对应x×(N-1)!第二位有N-1种选择又对应y×(N-2)!……一路乘下去刚好把一个排列映射成一个整数。3.2 在变进制上直接加M坐电梯到目标既然排列能映射成序号那从当前排列向后数M个本质上就是“当前排列序号 M”对应的那个排列。如果N不太大比如几百以内直接用康托展开算出序号加上M再做逆康托展开还原就能得到答案。但N到10000时(N-1)!这个数字早就超出long long的范围不能硬算阶乘。聪明一点的做法是不要真的去算那个巨大的序号而是模拟“在这个变进制数上加上M”的过程。这跟十进制加法一样从低位开始一位一位地加超出某一位的进制范围就向高位进位。区别只在于每一位的进制不一样所以叫变进制。我把具体算法写出来。首先求系数数组c[i]其中c[i]表示a[i]右边有多少个数字比a[i]小。接下来令cur M从数组最后一个位置往前处理把当前位的系数c[i]加上cur。这一位能取的最大范围是“右边剩余数字个数”更准确地说从右往左数第q个位置对应的取值个数是q第0个位置固定为0即最后一个位置只能取0。于是令c[i] c[i] % qcur c[i] / q其中q从2开始递增也就是右边的位置依次对应q2、3、4...。循环结束后新的c数组就是目标排列对应的系数。是不是有点绕我拿231这个排列M1来验证。231的系数是(1,1,0)。从右往左最右边一位系数0加上cur1得到1。这一位固定没有余地模1得0进位1。中间一位系数1加上进位1得到2。这一位的范围是{0,1}也就是能选2种模2得0进位1。最左边一位系数1加上进位1得到2。这一位范围是{0,1,2}能选3种模3得2进位0。于是新的系数是(2,0,0)。根据3.1的公式2×2! 0×1! 0×0! 4正好是312的编号。因为231的编号是3加1等于4所以目标排列就是312。整个计算过程与数字的加法进位完全一致只是进制不同而已。写代码的时候可以用一个整数数组直接在原系数上做进位不需要真算阶乘非常清爽。3.3 用树状数组还原目标排列进位完成后得到的是系数数组还需要还原成排列。还原过程其实很简单从左到右根据每一位的系数在当前还没使用的数字集合中选取第系数1小的数字。因为系数为x表示“在剩余数字中有x个数字比它小”所以它就是剩余数字中第x1小的那个。这里最直接的办法是开一个bool数组标记某个数字是否用过然后每次从1开始扫描到N找第x1个未使用的数字。但这样是O(N)找一个数字总复杂度O(N^2)N10000时就是1e8运气不好会超时。用树状数组维护“某个编号是否被使用”可以在O(log N)时间内完成“找第k个可用的数字”这件事。思路是用树状数组存储每个数字的剩余状态1表示还没被使用。给定系数c[i]要找的就是前缀和恰好等于c[i]1的最左位置这个可以用二分答案配合树状数组查询实现也可以直接在树状数组上做“树上二分”也就是在bit上找第k个1的位置。#include bits/stdc.h using namespace std; const int MAXN 10005; int n, m; int a[MAXN], c[MAXN]; int tree[MAXN]; int lowbit(int x) { return x -x; } void add(int idx, int val) { for (int i idx; i n; i lowbit(i)) { tree[i] val; } } int sum(int idx) { int res 0; for (int i idx; i 0; i - lowbit(i)) { res tree[i]; } return res; } // 在树状数组中找第k个1的位置 int kth(int k) { int pos 0; for (int i 20; i 0; --i) { int nxt pos (1 i); if (nxt n tree[nxt] k) { k - tree[nxt]; pos nxt; } } return pos 1; } int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%d, a[i]); } // 第一步计算每个位置右边比自己小的数字个数 // 用树状数组边插入边统计也可以直接暴力O(N^2) memset(tree, 0, sizeof(tree)); for (int i n; i 1; --i) { c[i] sum(a[i] - 1); add(a[i], 1); } // 第二步模拟进位加上m int base 2; for (int i n; i 1; --i) { c[i] m; m c[i] / base; c[i] % base; base; } // 第三步根据系数还原排列 memset(tree, 0, sizeof(tree)); for (int i 1; i n; i) { add(i, 1); } for (int i 1; i n; i) { int pos kth(c[i] 1); printf(%d , pos); add(pos, -1); } printf(\n); return 0; }我来解释几个关键细节。第一步求c[i]的时候从右往左遍历每次查询当前树状数组中小于a[i]的数字个数然后把a[i]本身插入。这样就得到了“右边比它小的数字个数”。第二步的进位从右往左base从2开始递增因为最右边一位永远只能取0倒数第二位只能取0或1再往前一位可以取0、1、2以此类推。第三步初始化树状数组全部为1表示所有数字都未使用然后依次取出第c[i]1小的数字取出来后标记为0。这个算法的总复杂度是O(N log N)N10000时非常快哪怕N开到1e6也能扛住。3.4 两种写法的硬碰硬对比对比维度STL next_permutation排列序号进位法代码长度很短十几行较长需要树状数组时间复杂度理论最坏O(NM)实际远快O(N log N)稳定原理难度低会用STL即可高需要理解康托展开与逆展开优点不易写错适合考场速战效率稳定可扩展到N很大缺点依赖STL遇到数据卡可能超时容易在进位、还原细节上出错从应试角度讲这两种方法都是正解。从学习角度讲我更推荐把进位法彻底弄懂因为它能帮你打通康托展开、逆康托展开、求第K小字典序排列等一系列问题。4. 常见问题与调试心得4.1 我明明照着文章写的为什么Wrong Answer这道题最常见的“想让代码通过但怎么都差一点”的坑我整理成了一张速查表症状可能原因解决办法结果总是比答案大一点多调用了一次next_permutation注意题目要求“后续第M个”不是“执行M1次”结果完全乱掉数组下标与迭代器区间传错next_permutation(a1, an1)是左闭右开不要写an进位法结果部分正确进位时base初始值写错从右往左base从2开始递增别从1开始进位法输出有重复或缺失还原系数时选了已使用的数字确认kth函数找到的是第c[i]1个未使用数字找完立刻删掉本地跑大样例超时用了O(N^2)暴力找第k小改用树状数组二分或直接在BIT上跳输出末尾多个空格每行输出后等多数OJ接受行尾空格但比赛建议控制格式其中“base从1开始”这个错误我记得特别清楚。为什么最后一位永远只能取0因为你已经确定到最后一个数字时剩下的数字只有一个它不可能是“比某个数字小”的第几个所以系数固定为0。从右往左第2位开始才有0/1两种选择所以base从2开始。4.2 推荐的对拍与压力测试技巧一道题写完光靠样例远远不够。我习惯写一个对拍器来验证。生成一个小N比如N8以内的随机排列用最暴力的办法枚举全排列数到目标位置再用你的算法算一遍对比结果是否一致。如果小数据没错再逐渐加大N测试性能。C写暴力验证非常简单先生成目标起始排列然后用next_permutation循环M次这个本身就可以当作暴力标准答案。然后再把进位法跑一边两个结果比对。如果N8、M100时结果都能对上基本可以判断算法核心没问题剩下的就是边界条件。性能测试部分我建议专门构造一个接近降序的排列比如N10000起始排列是987654321...这样的顺序M取10000。这种数据对STL方法的压力最大如果跑下来没超时说明这道题用STL确实是稳的。4.3 从这道题延伸出去的算法清单这道题虽然只是普及组但它的内核非常硬核。排列相关的几类问题完全可以串成一条学习线康托展开求一个排列在字典序中的编号常用于状态压缩DP做哈希。逆康托展开根据编号恢复排列上面的进位法本质上就是这个。求第K个字典序排列标答思路就是逆康托展开N大时用树状数组或线段树优化。可重集排列序列里允许重复元素时排列数的计算要用到多重集排列公式组合数选阶乘。部分排列从N个数字中选K个排列的问题编号方式和全排列相似但每一位选项范围更复杂。如果你把“火星人”完全吃透后面的这些算法会顺畅很多。因为变进制进位的核心思想就是“每一位的选项个数不同”而可重集、部分排列都是在这个思想上稍作修改。最后分享一个我的个人习惯我现在带学生刷题总会在讲完STL解法之后逼着他们亲手写一遍进位法就算题目用STL能过也必须写。原因很简单STL的next_permutation是别人做好的轮子你能用别人也能用但考场上万一题目升级成“给定一个10万位的大排列求后面第10万个排列”STL那套很可能就被数据按在地上摩擦。进位法虽然代码多一些但它逼着你理解排列的本质理解变进制理解树状数组的妙用。理解过一遍之后以后再遇到类似题心态完全不一样。还有一个小技巧当年我被“系数还原”卡住的时候喜欢拿N3把所有排列手写一遍然后对着纸演算进位过程。纸上画三分钟比盯着屏幕干想半小时效率高得多。如果你今天在这道题上栽了跟头别急着翻题解先把手上的N调成3或4把排列一张一张画出来再对比算法每一步的结果很多疑点会瞬间解开。