我第一次看到 P1088 这道题时第一反应是NOIP 2004 普及组名字叫火星人这题应该不难吧结果读题就绕了一下——火星人的计数方式不是十进制也不是二进制而是用排列的顺序来表示数。题目本质其实一句话就能说清给定一个 1 到 N 的排列把它看作全排列字典序中的某一个位置往后数 M 个输出新的排列。这道题非常适合用来打通全排列这条知识线从最直接的 STL 调用到手写 next_permutation再到康托展开和逆康托展开层层递进每一层都是能用在后续算法题里的硬通货。如果你在洛谷上做题或者在准备算法竞赛这篇内容可以帮你彻底吃透全排列相关的几类经典操作。我把自己的完整思考过程、代码实现和一些提交时的低级错误都写在这里适合从入门到进阶的读者参考。1. 火星人的计数方式到底是什么排列即数字先说题目本身。火星人有 N 个手指每个手指编号是 1 到 N他们就靠这 N 个手指的顺序来记录一个正整数。换句话说给定一个 [1, N] 的排列 a1, a2, ..., aN这个排列本身就代表了一个数。那这个数是怎么定的呢答案是所有 N! 个排列按字典序从小到大排好当前排列所在的位置就是它表示的数。这个设定对第一次接触的人来说有点抽象但用 N 3 举例子就非常直观排列表示的数1 2 311 3 222 1 332 3 143 1 253 2 16所以题目输入一个当前的排列再给一个 M要你算出往后数 M 个之后是什么排列。比如输入排列是 2 3 1对应数字 4如果 M 2那么 4 2 6对应的排列就是 3 2 1这就是答案。看明白这个例子之后就清楚了一个关键点这个所谓火星人的计数方式本质上就是全排列的字典序排名。你不需要真的去理解外星人的数学体系只需要知道在字典序序列中从当前排列向后走 M 步即可。这也意味着所有全排列相关的算法都可以直接套用过来。顺便说一句题目里保证加 M 之后的结果一定合法也就是说不会超过第 N! 个排列所以不需要额外处理越界情况。不过即使不越界你也得想清楚一个排列的字典序排名的取值范围是 1 到 N!而 N 可以到 10000N! 是一个天文数字根本不可能用普通整数存下来。这是后面所有设计的一个隐性约束。2. 直接调用 next_permutation 为什么能轻松过题拿到这道题最简单粗暴的思路就是既然要往后走 M 个排列那就调用 M 次 next_permutation 不就行了我第一次做这题时也担心会不会超时于是专门算了算复杂度。next_permutation 单次的时间复杂度是 O(N)需要执行 M 次所以总复杂度是 O(N * M)。题目中 N 的范围是 10000M 的范围比较小典型情况只有 100 左右那么 N * M 10000 * 100 1000000也就是一百万次操作。这个量级在现代 CPU 上就是毫秒级别稳稳通过。用 STL 的解法核心代码很短#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) cin a[i]; while (m--) { next_permutation(a.begin(), a.end()); } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }这个解法在洛谷上能 AC代码也短但我必须提醒一个新手特别容易犯的错误不要把输入排列先排序然后从最小排列开始执行 M 次。题目给的是一个已经被指定的起点你只能从它往后走不能先回到最小排列再重新数那样得到的结果和题目要求完全不是一回事。举个例子输入排列是 2 3 1M 2从它往后走两步是 3 2 1对应数字 6。如果先排序成 1 2 3再走两步变成 2 3 1这就直接做错了。STL 的 next_permutation 是从当前排列本身出发这正好符合题意所以你直接用就行千万别画蛇添足。既然 STL 解法这么简单那还有必要深挖吗有因为很多题目环境不允许你直接调 STL或者你需要在这种极简操作背后理解它的运行原理。更重要的是如果 M 的范围变大或者 N 的范围变大直接循环 M 次 next_permutation 就不一定扛得住了这个我在后面第 4 节会专门展开。3. 剖析 next_permutation字典序下一个排列的完整推导只会在代码里写 next_permutation(a.begin(), a.end()) 是不够的面试和笔试题里经常要求你手写这个函数。理解它的原理一点都不难关键是把字典序的规则想透。字典序比较两个排列时是从第一位开始逐个比较找到第一个不同的位置谁在这一位的数字小谁就排在前面。这和英语词典里单词排序的规则一样所以叫字典序。那从当前排列找字典序下一个排列逻辑上就是在不改变尽量长前缀的前提下把最后一个还能变大的位置变大然后让后面的部分变成最小的排列。这样做得到的一定是下一个排列因为任何改变更靠前的操作都会跳过多于一个排列。具体分四步走从右往左扫描找到第一个满足 a[i] a[i 1] 的位置 i。这个位置就是最后一个还能变大的位置。在 i 的右边找到最小的大于 a[i] 的数字 a[j]。交换 a[i] 和 a[j]。把 a[i 1] 到末尾这一段反转。这里要理解一个关键性质从左往右看第一次出现上升的边界是 i也就是说i 右边的序列一定是一个严格递减序列。所以第一步找到 i 后右侧已经是从大到小排好的。第二步在递减序列中找第一个比 a[i] 大的数字即可它就是最小的大于 a[i] 的数字。交换之后右侧依然保持递减顺序。第四步把这段递减序列反转得到递增序列这正好是右侧能形成的最小排列。举个例子排列是 1 5 4 2 3从右往左2 3所以 i 3a[i] 2右侧 [3] 中大于 2 的最小数字是 3交换得到 1 5 4 3 2反转 i 1 到末尾也就是反转空区间结果还是 1 5 4 3 2。但这个例子太简单了换一个更有意思的排列 1 5 4 3 2从右往左5 44 33 2都递减直到 1 5所以 i 0a[i] 1右侧 [5, 4, 3, 2] 中最小的大于 1 的数字是 2交换 1 和 2得到 2 5 4 3 1反转 [5, 4, 3, 1]得到 2 1 3 4 5。所以 1 5 4 3 2 的下一个排列是 2 1 3 4 5。你可以数一下1 5 4 3 2 是字典序第 119 个0-based 排名2 1 3 4 5 正好是第 120 个即最后一个完全对得上。手写版本如下bool next_permutation_manual(vectorint a) { int n (int)a.size(); int i n - 2; while (i 0 a[i] a[i 1]) i--; if (i 0) return false; // 已经是最后一个排列 int j n - 1; while (a[j] a[i]) j--; swap(a[i], a[j]); reverse(a.begin() i 1, a.end()); return true; }注意几个边界第一步找 i 的时候条件是 a[i] a[i 1] 就继续往前等于是跳过所有递减部分如果 i 变成 -1说明整个排列完全递减也就是没有下一个排列了返回 false。第二步找 j 时因为右侧是递减的所以从末尾往左找到的第一个大于 a[i] 的数就是目标不需要显式比较大小找最小直接从右往左找就行。说实话手写一遍之后你对 STL 的信任度都会上升一层因为它内部实现基本就是这样没有任何魔法。4. 从看似合理的优化到康托展开与逆康托展开等下我上面说直接循环 M 次 next_permutation 能过题但如果我告诉你有人试着只对排列末尾截取一段做 next_permutation来优化然后踩坑了你会不会觉得意外我当初就干过这事还花了不少时间调试。当时我的想法很直接既然 M 很小那排列的前面大部分位置根本不会变只有最后某个长度的子序列在不断轮转。那是不是把最后 t 个数字截出来只对这一小段做 M 次 next_permutation前面保持不变就能省下大量时间这个思路听着挺美但有一个致命反例。比如排列 3 5 4 2 1取后三位 4 2 1 做 next_permutation。4 2 1 是一个递减序列已经是后三位能组成的最大排列没有下一个了。可是整个排列 3 5 4 2 1 的下一个排列是 4 1 2 3 5因为 4 2 1 无法继续变大时进位到了更前面的 5与 3 交换后重新整理了后缀。如果你只操作后三位得到的是完全错误的结果。这个反例说明不能简单地截取末尾固定长度来做局部模拟因为你判断不了当前截取段是否已经处于局部最大状态一旦进位影响范围就会向前扩展。要严谨地解决这个问题就得回到排列和序号的本质关系上来。这里引出康托展开和逆康托展开。康托展开解决的是给一个排列求它是第几个排列的问题。0-based 排名计算公式如下rank ∑_{i1}^{n} s_i × (n - i)!其中 s_i 表示第 i 个位置右侧有多少个比 a[i] 小的数字。理解这个公式的关键在于逐位考虑当你在第 i 位确定了数字 a[i] 之后如果这一位没有填 a[i]而是填了一个更小的数字那么后面 (n - i) 个位置可以任意排列每种排列都会让当前排列的排名变大 (n - i)! 个。举个例子排列 2 3 1i 1a[1] 2右侧比 2 小的是 1所以 s1 1贡献 1 × 2! 2i 2a[2] 3右侧比 3 小的是 1所以 s2 1贡献 1 × 1! 1i 3a[3] 1s3 0rank 2 1 30-based也就是说它是第 4 个排列和前面表格里 2 3 1 对应数字 4 完全一致。逆康托展开就是反过来给定排名还原排列。做法是维护一个候选数字列表初始为 1 到 N然后从高位到低位依次确定每一位的数字令 rank_0 rank - 1如果排名是 1-based对于第 i 位计算 idx rank_0 / (n - i)!从候选列表中取出第 idx 个数字下标从 0 开始更新 rank_0 rank_0 % (n - i)!从候选列表中删除该数字继续下一位。看似和这道题关系不大其实关系很大。回到火星人这道题如果 M 不是 100 而是非常大的数比如 10^18那么循环 M 次 next_permutation 就完全不可能了。此时正解思路应该是算出给定排列的排名 rank0加上 M 得到新的排名 rank1再用逆康托展开还原排列。但问题来了N 很大时 rank 会超过任何内置整数类型。解决思路是不需要完整算出 rank0只需要维护一个变进制数表示。观察康托展开公式rank s1 × (n-1)! s2 × (n-2)! ... sn × 0!这其实就是一个每位权值不同的变进制数其中第 i 位的取值范围是 0 到 n - i。对 rank 加 M等价于对这个变进制数加 M。在这个变进制系统中做加法时从低位向高位逐位处理先把 M 拆成对应权值的分量或者直接逐位加上并进位。M 是普通十进制整数拆分的公式是从低到高依次取 m % k、m / kk 从 2 开始递增直到 m 变成 0。因为最低一位权值是 0! 1但这一位数恒为 0实际从权值 1! 对应的位开始处理。拆 M 例如 M 55 % 2 1作为权值 1! 位的增量5 / 2 22 % 3 2作为权值 2! 位的增量2 / 3 0所以 5 1 × 1! 2 × 2!变进制表示的低位到高位是 [1, 2]。然后把 M 的变进制分量加到原排列的康托展开分量上处理进位最后用逆康托展开还原排列。由于 M 的范围有限涉及到进位的位数不会超过使 k! M 的最小 k 太多所以可以高效处理。不过这种写法代码量大很多对本题来说是杀鸡用牛刀了。我把康托展开的正向实现也贴一下方便对照理解long long cantor(const vectorint a) { int n (int)a.size(); vectorint bit(n 1); long long rank 0, fact 1; for (int i n - 1; i 0; i--) { int smaller 0; for (int j i 1; j n; j) { if (a[j] a[i]) smaller; } rank smaller * fact; fact * (n - i); } return rank; }这里类比的思路是把排列看成一本厚字典里的一个词康托展开是查页码逆康托展开是按页码翻词。火星人只是把这个页码当成了要计数的数字而已。5. 完整代码与提交中的常见坑回到这道题本身我建议至少掌握两种提交写法一种是直接依赖 STL代码最短一种是手写 next_permutation遇到不能用 STL 的环境也不慌。下面是我本人在洛谷提交过的完整版本。C 完整实现短版本#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } while (m--) { next_permutation(a.begin(), a.end()); } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }C 完整实现手写 next_permutation 版本#include bits/stdc.h using namespace std; bool nextPermutation(vectorint a) { int n (int)a.size(); int i n - 2; while (i 0 a[i] a[i 1]) i--; if (i 0) return false; int j n - 1; while (a[j] a[i]) j--; swap(a[i], a[j]); reverse(a.begin() i 1, a.end()); return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } while (m--) { nextPermutation(a); } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }Python 完整实现import sys def next_permutation(a): n len(a) i n - 2 while i 0 and a[i] a[i 1]: i - 1 if i 0: return False j n - 1 while a[j] a[i]: j - 1 a[i], a[j] a[j], a[i] a[i 1:] reversed(a[i 1:]) return True def main(): data sys.stdin.read().split() n int(data[0]) m int(data[1]) a list(map(int, data[2:2 n])) for _ in range(m): next_permutation(a) print( .join(map(str, a))) if __name__ __main__: main()提交这道题的过程里我踩过几个特别蠢但也很典型的坑罗列在这里给大家提个醒第一个坑是输入顺序。题目先给 N再给 M最后给排列。有人会习惯性先读 M 再读 N或者把排列的长度读错结果后面一系列数组越界。这种题考查的不是读入读入错了是真的冤枉。建议写完代码后先看一眼样例确保输入变量对应正确。第二个坑是输出格式。要求是输出 N 个数数字之间用空格分隔末尾有没有多余空格一般不影响判定。但如果你输出成每个数字一行那就会直接 WA。还有人在最后少输出了换行虽然很多判定程序容忍末尾没有换行但保险起见还是加上。第三个坑是循环 M 次 next_permutation里的边界。如果 M 是 0循环一次都不执行直接输出原始排列这个逻辑在代码里天然正确不用特殊处理。但如果用 while (m--) 这种写法m 会被减到负数之后再用 m 就会出问题。这道题里 m 用完就不用了所以没事但如果你后面还有用到 m建议用 for 循环。第四个坑是手写 next_permutation 时容易在找 j 的地方写错。因为在 i 右侧是递减序列所以从右往左找到的第一个大于 a[i] 的数就是目标不需要额外变量去维护当前最小的大于 a[i] 的数。但如果你的环境不是递减序列比如你错误的实现导致右侧没被反转那就可能选错交换对象。所以手写时一定要确保前面找 i 的逻辑完全正确左侧跳过的部分必须是 a[i] a[i 1]不能是 a[i] a[i 1]。用 还是 很关键遇到有重复元素时区别特别明显。虽然这道题的排列是 1 到 N 的全排列没有重复元素但为了写出通用性更强的代码我建议还是用 。第五个坑是关于复杂度的心理预期。有些人看到 N 10000就以为 O(N * M) 过不了非得去搞康托展开结果把自己绕晕。实际上 10000 * 100 1e6 这个量级非常小根本不需要担心。真正需要担心的反而是数组开小、递归爆栈、输入输出没加速这类基础问题。还有一个小技巧如果你在做题时想验证自己的结果对不对可以拿 N 3、N 4 的小数据手动枚举所有排列然后跑代码对照。比如 N 3 的全部排列是 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1拿任意一个起点和 M 值手推一遍再和程序输出比基本能确认算法没问题。最后再分享点个人感受。P1088 这道题虽然名字唬人但它其实是全排列领域里最好的入门题之一。从 STL 调用入手你可以一路延伸到手写 next_permutation再到康托展开、逆康托展开最后甚至能理解变进制数是怎么运作的。很多看起来复杂的排列计数问题追根溯源都是这套东西。我后来在 Codeforces 上遇到一道 Permutation 相关的题第一反应就是想起这道火星人直接用逆康托展开的思路做出来了。所以别嫌弃它简单把它吃透后面的路会顺很多。
全排列与康托展开：从火星人P1088到next_permutation的深入解析
我第一次看到 P1088 这道题时第一反应是NOIP 2004 普及组名字叫火星人这题应该不难吧结果读题就绕了一下——火星人的计数方式不是十进制也不是二进制而是用排列的顺序来表示数。题目本质其实一句话就能说清给定一个 1 到 N 的排列把它看作全排列字典序中的某一个位置往后数 M 个输出新的排列。这道题非常适合用来打通全排列这条知识线从最直接的 STL 调用到手写 next_permutation再到康托展开和逆康托展开层层递进每一层都是能用在后续算法题里的硬通货。如果你在洛谷上做题或者在准备算法竞赛这篇内容可以帮你彻底吃透全排列相关的几类经典操作。我把自己的完整思考过程、代码实现和一些提交时的低级错误都写在这里适合从入门到进阶的读者参考。1. 火星人的计数方式到底是什么排列即数字先说题目本身。火星人有 N 个手指每个手指编号是 1 到 N他们就靠这 N 个手指的顺序来记录一个正整数。换句话说给定一个 [1, N] 的排列 a1, a2, ..., aN这个排列本身就代表了一个数。那这个数是怎么定的呢答案是所有 N! 个排列按字典序从小到大排好当前排列所在的位置就是它表示的数。这个设定对第一次接触的人来说有点抽象但用 N 3 举例子就非常直观排列表示的数1 2 311 3 222 1 332 3 143 1 253 2 16所以题目输入一个当前的排列再给一个 M要你算出往后数 M 个之后是什么排列。比如输入排列是 2 3 1对应数字 4如果 M 2那么 4 2 6对应的排列就是 3 2 1这就是答案。看明白这个例子之后就清楚了一个关键点这个所谓火星人的计数方式本质上就是全排列的字典序排名。你不需要真的去理解外星人的数学体系只需要知道在字典序序列中从当前排列向后走 M 步即可。这也意味着所有全排列相关的算法都可以直接套用过来。顺便说一句题目里保证加 M 之后的结果一定合法也就是说不会超过第 N! 个排列所以不需要额外处理越界情况。不过即使不越界你也得想清楚一个排列的字典序排名的取值范围是 1 到 N!而 N 可以到 10000N! 是一个天文数字根本不可能用普通整数存下来。这是后面所有设计的一个隐性约束。2. 直接调用 next_permutation 为什么能轻松过题拿到这道题最简单粗暴的思路就是既然要往后走 M 个排列那就调用 M 次 next_permutation 不就行了我第一次做这题时也担心会不会超时于是专门算了算复杂度。next_permutation 单次的时间复杂度是 O(N)需要执行 M 次所以总复杂度是 O(N * M)。题目中 N 的范围是 10000M 的范围比较小典型情况只有 100 左右那么 N * M 10000 * 100 1000000也就是一百万次操作。这个量级在现代 CPU 上就是毫秒级别稳稳通过。用 STL 的解法核心代码很短#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) cin a[i]; while (m--) { next_permutation(a.begin(), a.end()); } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }这个解法在洛谷上能 AC代码也短但我必须提醒一个新手特别容易犯的错误不要把输入排列先排序然后从最小排列开始执行 M 次。题目给的是一个已经被指定的起点你只能从它往后走不能先回到最小排列再重新数那样得到的结果和题目要求完全不是一回事。举个例子输入排列是 2 3 1M 2从它往后走两步是 3 2 1对应数字 6。如果先排序成 1 2 3再走两步变成 2 3 1这就直接做错了。STL 的 next_permutation 是从当前排列本身出发这正好符合题意所以你直接用就行千万别画蛇添足。既然 STL 解法这么简单那还有必要深挖吗有因为很多题目环境不允许你直接调 STL或者你需要在这种极简操作背后理解它的运行原理。更重要的是如果 M 的范围变大或者 N 的范围变大直接循环 M 次 next_permutation 就不一定扛得住了这个我在后面第 4 节会专门展开。3. 剖析 next_permutation字典序下一个排列的完整推导只会在代码里写 next_permutation(a.begin(), a.end()) 是不够的面试和笔试题里经常要求你手写这个函数。理解它的原理一点都不难关键是把字典序的规则想透。字典序比较两个排列时是从第一位开始逐个比较找到第一个不同的位置谁在这一位的数字小谁就排在前面。这和英语词典里单词排序的规则一样所以叫字典序。那从当前排列找字典序下一个排列逻辑上就是在不改变尽量长前缀的前提下把最后一个还能变大的位置变大然后让后面的部分变成最小的排列。这样做得到的一定是下一个排列因为任何改变更靠前的操作都会跳过多于一个排列。具体分四步走从右往左扫描找到第一个满足 a[i] a[i 1] 的位置 i。这个位置就是最后一个还能变大的位置。在 i 的右边找到最小的大于 a[i] 的数字 a[j]。交换 a[i] 和 a[j]。把 a[i 1] 到末尾这一段反转。这里要理解一个关键性质从左往右看第一次出现上升的边界是 i也就是说i 右边的序列一定是一个严格递减序列。所以第一步找到 i 后右侧已经是从大到小排好的。第二步在递减序列中找第一个比 a[i] 大的数字即可它就是最小的大于 a[i] 的数字。交换之后右侧依然保持递减顺序。第四步把这段递减序列反转得到递增序列这正好是右侧能形成的最小排列。举个例子排列是 1 5 4 2 3从右往左2 3所以 i 3a[i] 2右侧 [3] 中大于 2 的最小数字是 3交换得到 1 5 4 3 2反转 i 1 到末尾也就是反转空区间结果还是 1 5 4 3 2。但这个例子太简单了换一个更有意思的排列 1 5 4 3 2从右往左5 44 33 2都递减直到 1 5所以 i 0a[i] 1右侧 [5, 4, 3, 2] 中最小的大于 1 的数字是 2交换 1 和 2得到 2 5 4 3 1反转 [5, 4, 3, 1]得到 2 1 3 4 5。所以 1 5 4 3 2 的下一个排列是 2 1 3 4 5。你可以数一下1 5 4 3 2 是字典序第 119 个0-based 排名2 1 3 4 5 正好是第 120 个即最后一个完全对得上。手写版本如下bool next_permutation_manual(vectorint a) { int n (int)a.size(); int i n - 2; while (i 0 a[i] a[i 1]) i--; if (i 0) return false; // 已经是最后一个排列 int j n - 1; while (a[j] a[i]) j--; swap(a[i], a[j]); reverse(a.begin() i 1, a.end()); return true; }注意几个边界第一步找 i 的时候条件是 a[i] a[i 1] 就继续往前等于是跳过所有递减部分如果 i 变成 -1说明整个排列完全递减也就是没有下一个排列了返回 false。第二步找 j 时因为右侧是递减的所以从末尾往左找到的第一个大于 a[i] 的数就是目标不需要显式比较大小找最小直接从右往左找就行。说实话手写一遍之后你对 STL 的信任度都会上升一层因为它内部实现基本就是这样没有任何魔法。4. 从看似合理的优化到康托展开与逆康托展开等下我上面说直接循环 M 次 next_permutation 能过题但如果我告诉你有人试着只对排列末尾截取一段做 next_permutation来优化然后踩坑了你会不会觉得意外我当初就干过这事还花了不少时间调试。当时我的想法很直接既然 M 很小那排列的前面大部分位置根本不会变只有最后某个长度的子序列在不断轮转。那是不是把最后 t 个数字截出来只对这一小段做 M 次 next_permutation前面保持不变就能省下大量时间这个思路听着挺美但有一个致命反例。比如排列 3 5 4 2 1取后三位 4 2 1 做 next_permutation。4 2 1 是一个递减序列已经是后三位能组成的最大排列没有下一个了。可是整个排列 3 5 4 2 1 的下一个排列是 4 1 2 3 5因为 4 2 1 无法继续变大时进位到了更前面的 5与 3 交换后重新整理了后缀。如果你只操作后三位得到的是完全错误的结果。这个反例说明不能简单地截取末尾固定长度来做局部模拟因为你判断不了当前截取段是否已经处于局部最大状态一旦进位影响范围就会向前扩展。要严谨地解决这个问题就得回到排列和序号的本质关系上来。这里引出康托展开和逆康托展开。康托展开解决的是给一个排列求它是第几个排列的问题。0-based 排名计算公式如下rank ∑_{i1}^{n} s_i × (n - i)!其中 s_i 表示第 i 个位置右侧有多少个比 a[i] 小的数字。理解这个公式的关键在于逐位考虑当你在第 i 位确定了数字 a[i] 之后如果这一位没有填 a[i]而是填了一个更小的数字那么后面 (n - i) 个位置可以任意排列每种排列都会让当前排列的排名变大 (n - i)! 个。举个例子排列 2 3 1i 1a[1] 2右侧比 2 小的是 1所以 s1 1贡献 1 × 2! 2i 2a[2] 3右侧比 3 小的是 1所以 s2 1贡献 1 × 1! 1i 3a[3] 1s3 0rank 2 1 30-based也就是说它是第 4 个排列和前面表格里 2 3 1 对应数字 4 完全一致。逆康托展开就是反过来给定排名还原排列。做法是维护一个候选数字列表初始为 1 到 N然后从高位到低位依次确定每一位的数字令 rank_0 rank - 1如果排名是 1-based对于第 i 位计算 idx rank_0 / (n - i)!从候选列表中取出第 idx 个数字下标从 0 开始更新 rank_0 rank_0 % (n - i)!从候选列表中删除该数字继续下一位。看似和这道题关系不大其实关系很大。回到火星人这道题如果 M 不是 100 而是非常大的数比如 10^18那么循环 M 次 next_permutation 就完全不可能了。此时正解思路应该是算出给定排列的排名 rank0加上 M 得到新的排名 rank1再用逆康托展开还原排列。但问题来了N 很大时 rank 会超过任何内置整数类型。解决思路是不需要完整算出 rank0只需要维护一个变进制数表示。观察康托展开公式rank s1 × (n-1)! s2 × (n-2)! ... sn × 0!这其实就是一个每位权值不同的变进制数其中第 i 位的取值范围是 0 到 n - i。对 rank 加 M等价于对这个变进制数加 M。在这个变进制系统中做加法时从低位向高位逐位处理先把 M 拆成对应权值的分量或者直接逐位加上并进位。M 是普通十进制整数拆分的公式是从低到高依次取 m % k、m / kk 从 2 开始递增直到 m 变成 0。因为最低一位权值是 0! 1但这一位数恒为 0实际从权值 1! 对应的位开始处理。拆 M 例如 M 55 % 2 1作为权值 1! 位的增量5 / 2 22 % 3 2作为权值 2! 位的增量2 / 3 0所以 5 1 × 1! 2 × 2!变进制表示的低位到高位是 [1, 2]。然后把 M 的变进制分量加到原排列的康托展开分量上处理进位最后用逆康托展开还原排列。由于 M 的范围有限涉及到进位的位数不会超过使 k! M 的最小 k 太多所以可以高效处理。不过这种写法代码量大很多对本题来说是杀鸡用牛刀了。我把康托展开的正向实现也贴一下方便对照理解long long cantor(const vectorint a) { int n (int)a.size(); vectorint bit(n 1); long long rank 0, fact 1; for (int i n - 1; i 0; i--) { int smaller 0; for (int j i 1; j n; j) { if (a[j] a[i]) smaller; } rank smaller * fact; fact * (n - i); } return rank; }这里类比的思路是把排列看成一本厚字典里的一个词康托展开是查页码逆康托展开是按页码翻词。火星人只是把这个页码当成了要计数的数字而已。5. 完整代码与提交中的常见坑回到这道题本身我建议至少掌握两种提交写法一种是直接依赖 STL代码最短一种是手写 next_permutation遇到不能用 STL 的环境也不慌。下面是我本人在洛谷提交过的完整版本。C 完整实现短版本#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } while (m--) { next_permutation(a.begin(), a.end()); } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }C 完整实现手写 next_permutation 版本#include bits/stdc.h using namespace std; bool nextPermutation(vectorint a) { int n (int)a.size(); int i n - 2; while (i 0 a[i] a[i 1]) i--; if (i 0) return false; int j n - 1; while (a[j] a[i]) j--; swap(a[i], a[j]); reverse(a.begin() i 1, a.end()); return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } while (m--) { nextPermutation(a); } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }Python 完整实现import sys def next_permutation(a): n len(a) i n - 2 while i 0 and a[i] a[i 1]: i - 1 if i 0: return False j n - 1 while a[j] a[i]: j - 1 a[i], a[j] a[j], a[i] a[i 1:] reversed(a[i 1:]) return True def main(): data sys.stdin.read().split() n int(data[0]) m int(data[1]) a list(map(int, data[2:2 n])) for _ in range(m): next_permutation(a) print( .join(map(str, a))) if __name__ __main__: main()提交这道题的过程里我踩过几个特别蠢但也很典型的坑罗列在这里给大家提个醒第一个坑是输入顺序。题目先给 N再给 M最后给排列。有人会习惯性先读 M 再读 N或者把排列的长度读错结果后面一系列数组越界。这种题考查的不是读入读入错了是真的冤枉。建议写完代码后先看一眼样例确保输入变量对应正确。第二个坑是输出格式。要求是输出 N 个数数字之间用空格分隔末尾有没有多余空格一般不影响判定。但如果你输出成每个数字一行那就会直接 WA。还有人在最后少输出了换行虽然很多判定程序容忍末尾没有换行但保险起见还是加上。第三个坑是循环 M 次 next_permutation里的边界。如果 M 是 0循环一次都不执行直接输出原始排列这个逻辑在代码里天然正确不用特殊处理。但如果用 while (m--) 这种写法m 会被减到负数之后再用 m 就会出问题。这道题里 m 用完就不用了所以没事但如果你后面还有用到 m建议用 for 循环。第四个坑是手写 next_permutation 时容易在找 j 的地方写错。因为在 i 右侧是递减序列所以从右往左找到的第一个大于 a[i] 的数就是目标不需要额外变量去维护当前最小的大于 a[i] 的数。但如果你的环境不是递减序列比如你错误的实现导致右侧没被反转那就可能选错交换对象。所以手写时一定要确保前面找 i 的逻辑完全正确左侧跳过的部分必须是 a[i] a[i 1]不能是 a[i] a[i 1]。用 还是 很关键遇到有重复元素时区别特别明显。虽然这道题的排列是 1 到 N 的全排列没有重复元素但为了写出通用性更强的代码我建议还是用 。第五个坑是关于复杂度的心理预期。有些人看到 N 10000就以为 O(N * M) 过不了非得去搞康托展开结果把自己绕晕。实际上 10000 * 100 1e6 这个量级非常小根本不需要担心。真正需要担心的反而是数组开小、递归爆栈、输入输出没加速这类基础问题。还有一个小技巧如果你在做题时想验证自己的结果对不对可以拿 N 3、N 4 的小数据手动枚举所有排列然后跑代码对照。比如 N 3 的全部排列是 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1拿任意一个起点和 M 值手推一遍再和程序输出比基本能确认算法没问题。最后再分享点个人感受。P1088 这道题虽然名字唬人但它其实是全排列领域里最好的入门题之一。从 STL 调用入手你可以一路延伸到手写 next_permutation再到康托展开、逆康托展开最后甚至能理解变进制数是怎么运作的。很多看起来复杂的排列计数问题追根溯源都是这套东西。我后来在 Codeforces 上遇到一道 Permutation 相关的题第一反应就是想起这道火星人直接用逆康托展开的思路做出来了。所以别嫌弃它简单把它吃透后面的路会顺很多。
