题解：P5367 【模板】康托展开

ICU_midway_azuma · 2025-08-28 22:41:27 · 题解

康托展开，即求一个排列在其全排列中，按字典序排序后所处的位置。

如，1\sim 3 的全排列中：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

1 3 2 排在第 2 位。

考虑逐位比对的方法：

如对于排列 2 3 1，分析过程如下：

第 1 位是 2，比其更小的数有 1（所有首位小于 2 的排列的字典序一定比 2 3 1 小），该位结果为 1\times 2!=2。

第 2 位是 3，比其更小的数有 1 和 2，但 2 我们已经用过了（上一位比 2 更小的已经在上一步被统计过，比 2 更大的不被统计，故这里只统计上一位为 2 的情况），所以比其更小的数有 1 个，该位结果为 1\times 1!=1。

最后一位以此类推，没有比 1 更小的数，该位结果为 0\times 0!=0。

比 2 3 1 字典序小的排列有 2+1+0=3 个，排在第 4 位。

综上，我们总结：

设排列为 a_1,a_2,\cdots,a_n，r_i 为 a_1,a_2,\cdots,a_{i-1} 中小于 a_i 的数的数量。

则第 i 位的计算结果为 (a_i-r_i-1)\times (n-i)!。