P1088 [NOIP 2004 普及组] 火星人与康托展开

变进制数

我们的目标是把全排列转化成一个变进制数，以方便我们进行加法。对于第 i 根手指，它有 n−i+1 种选择，根据位值原理，要想让每个数对应一个全排列，就要让这一位数是 n−i+1 进制的。那么，整个过程分为三步：

1. 将火星数变成变进制数
2. 将变进制数加上 m
3. 将变进制数变成火星数

实例

我们来看一个实例： 将 1,4,5,2,3 变成变进制数：

首位 1 是 5 种选择 {1,2,3,4,5} 的第 1 种，故变为 0（从0开始）;
次位 4 是 4 种选择 {2,3,4,5} 的第 3 种，故变为 2;
中间位 5 是 3 种选择 {2,3,5} 的第 3 种，故变为 2;
次低位 2 是 2 种选择 {2,3} 的第 1 种，故变为 0;
末位 3 是 1 种选择 {3} 的第 1 种，故变为 0;
最后，排列 1,4,5,2,3 变成了(02200)。
​

接下来给它加上 3 变成 (02203)，并处理进位：

末位是 1 进制的，进 3 得 (02230)；
次低位是 2 进制的，满 2 进一得 (02310)；
中间位是 3 进制的，满 3 进一得 (03010)；
次位是 4 进制的，3<4，不进位，得 (03010)；
最后将 (03010) 变回火星数。

首位 0 表示这位应选择 {1,2,3,4,5} 的第 1 种，即 1；
次位 3 表示这位应选择 {2,3,4,5} 的第 4 种（1 被选过了），即 5；
中间位 0 表示这位应选择 {2,3,4} 的第 1 种，即 2；
次低位 1 表示这位应选择 {3,4} 的第 2 种，即 4；
末位 0 表示这位应选择 {3} 的第 1 种，即 3；
所以本题答案为 14523 +3= 15243。

以上摘自洛谷题解，作者：yummy

流程图解