当年在考场上第一次看到“火星人”这道题，心里又惊又喜。惊的是题面很有意思，外星人用手指数数，每个手指还都有自己的编号；喜的是它本质上就是全排列，字典序的下一个排列，这不就是当年教科书上“求后继排列”的经典问题吗？结果真动手写的时候，我卡了挺久。因为N和M都可以到10000，直接傻乎乎地从第一个排列开始枚举到目标位置，根本不可能；而如果只会用DFS全排列去“数”，N一大早就爆了。
这篇文章就从洛谷P1088这道题出发，把“给定一个排列，求它后面第M个字典序排列”这件事彻底讲清楚。既有考场上一行STL带走的偷懒做法，也有原理层面的排列序号进位法。不管你是备战NOIP、CSP-J/S的选手，还是刚学全排列、康托展开的初学者，都能找到自己能用的东西。
1. 题目解读与核心难点
1.1 火星人的手指密码到底是什么
先还原一下题面：火星人有一排N根手指，每根手指都有一个不重复的编号，从1到N。他们计数的方式很特别，把手指从左到右排成一列，用一个排列来表示一个数。所有的排列按照字典序从小到大排列好，比如N=3的时候就是123、132、213、231、312、321这样一路排下去。外星人会先伸出某个排列，然后告诉你“我要继续往后数M个数”，你要算出他最后摆出来的那个排列是什么。
输入给的是N、M，以及当前伸出的那个排列。N和M的范围都是10000以内。也就是说，N=10000、M=10000是可能出现的，而且题目只给一个测试点，时限一般是1秒左右。这不是一道让你去脑补“外星人有多神奇”的题，它考的就是排列生成、字典序以及如何处理大规模数据。
1.2 为什么不能直接从第一个排列开始数
很多新手第一反应是：既然所有排列已经按字典序排好了，那我用搜索把从123...N开始的排列一个一个生成出来，数到目标位置不就行了？这个思路在N很小的时候完全成立。N=3、N=4的时候，DFS把全排列枚举出来，再从头找目标排列的下M个，完全没问题。
但问题是N最大到10000。全排列的个数是N!，这个数字增长得极其恐怖，N=10就已经300多万个，N=10000根本不可能一一枚举。所以这道题考查的重点不是“生成全排列再查找”，而是“已知一个排列，如何在这个有序的排列序列中向后跳跃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. 思路A：STL next_permutation 通关（最简单写法）
2.1 next_permutation 到底做了什么
C++的STL里有一个函数叫next_permutation，它做的事情就是：对于一个数组表示的排列，原地修改它，使它变成字典序中的下一个排列。如果当前排列已经是字典序中最大的那个，比如N=3时的321，函数会返回false，并把数组改成最小的排列123。
它的原理其实只有三步：
- 从后往前找到第一个满足a[i] < a[i+1]的位置i，这个位置就是需要变动的“关键位置”。如果整个数组从后往前一直是降序，说明已经不存在更大的排列。
- 再从后往前找到第一个比a[i]大的元素a[j]。
- 交换a[i]和a[j]，然后把i+1到末尾这一段反转。因为这段原本是降序，反转后变成升序，刚好得到字典序中紧挨着的下一个排列。
举个例子，123的下一个排列是132。从后往前看，2 < 3，所以i指向2这个位置，然后从后往前找第一个比2大的数，找到3，交换得到132，然后i+1到末尾只有一位，不用反转，完成。
整个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开始存储时，就是a+1到a+n+1。如果谁把右边界写成a+n，那永远只会对前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是“一步一步走”，那进位法就是“坐电梯直达目标层”。要理解它，先得明白一个很漂亮的性质：任何一个排列，都能唯一转换成一个“变进制数”。
这个变进制数每一位表示的含义是：当前这个位置上，右边剩下没有用过的数字中，有多少个比它小。举个N=3的例子，看排列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号是123，1号是132，2号是213，3号正好是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] % q，cur = c[i] / q，其中q从2开始递增，也就是右边的位置依次对应q=2、3、4...。
- 循环结束后，新的c数组就是目标排列对应的系数。
是不是有点绕？我拿231这个排列，M=1来验证。231的系数是(1,1,0)。从右往左：
- 最右边一位系数0，加上cur=1，得到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个数字比它小”，所以它就是剩余数字中第x+1小的那个。
这里最直接的办法是开一个bool数组标记某个数字是否用过，然后每次从1开始扫描到N找第x+1个未使用的数字。但这样是O(N)找一个数字，总复杂度O(N^2)，N=10000时就是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)，N=10000时非常快，哪怕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个”，不是“执行M+1次” |
| 结果完全乱掉 | 数组下标与迭代器区间传错 | next_permutation(a+1, a+n+1)是左闭右开，不要写a+n |
| 进位法结果部分正确 | 进位时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（比如N=8以内）的随机排列，用最暴力的办法枚举全排列数到目标位置，再用你的算法算一遍，对比结果是否一致。如果小数据没错，再逐渐加大N测试性能。
C++写暴力验证非常简单：先生成目标起始排列，然后用next_permutation循环M次，这个本身就可以当作暴力标准答案。然后再把进位法跑一边，两个结果比对。如果N=8、M=100时结果都能对上，基本可以判断算法核心没问题，剩下的就是边界条件。
性能测试部分，我建议专门构造一个接近降序的排列，比如N=10000，起始排列是987654321...这样的顺序，M取10000。这种数据对STL方法的压力最大，如果跑下来没超时，说明这道题用STL确实是稳的。
4.3 从这道题延伸出去的算法清单
这道题虽然只是普及组，但它的内核非常硬核。排列相关的几类问题，完全可以串成一条学习线：
- 康托展开：求一个排列在字典序中的编号，常用于状态压缩DP做哈希。
- 逆康托展开：根据编号恢复排列，上面的进位法本质上就是这个。
- 求第K个字典序排列：标答思路就是逆康托展开，N大时用树状数组或线段树优化。
- 可重集排列：序列里允许重复元素时，排列数的计算要用到多重集排列公式，组合数选阶乘。
- 部分排列：从N个数字中选K个排列的问题，编号方式和全排列相似但每一位选项范围更复杂。
如果你把“火星人”完全吃透，后面的这些算法会顺畅很多。因为变进制进位的核心思想，就是“每一位的选项个数不同”，而可重集、部分排列都是在这个思想上稍作修改。
最后分享一个我的个人习惯
我现在带学生刷题，总会在讲完STL解法之后，逼着他们亲手写一遍进位法，就算题目用STL能过也必须写。原因很简单：STL的next_permutation是别人做好的轮子，你能用，别人也能用，但考场上万一题目升级成“给定一个10万位的大排列，求后面第10万个排列”，STL那套很可能就被数据按在地上摩擦。进位法虽然代码多一些，但它逼着你理解排列的本质，理解变进制，理解树状数组的妙用。理解过一遍之后，以后再遇到类似题，心态完全不一样。
还有一个小技巧：当年我被“系数还原”卡住的时候，喜欢拿N=3把所有排列手写一遍，然后对着纸演算进位过程。纸上画三分钟，比盯着屏幕干想半小时效率高得多。如果你今天在这道题上栽了跟头，别急着翻题解，先把手上的N调成3或4，把排列一张一张画出来，再对比算法每一步的结果，很多疑点会瞬间解开。
