康托展开原理与C++实现：排列与序号高效转换

1. 题目解析与算法选择

这个题目本质上考察的是排列与康托展开（Cantor Expansion）的应用。题目要求我们实现两种操作：根据排列序号生成排列（P命令），以及根据排列计算其序号（Q命令）。对于N≤20的情况，直接生成所有排列显然不可行（20!的排列数量过于庞大），因此我们需要更高效的数学方法。

康托展开正是解决这类问题的利器。它能够在O(n²)时间复杂度内完成排列与序号的相互转换，完美适配题目要求。康托展开的核心思想是将排列映射到一个唯一的序号，而逆康托展开则可以根据序号还原出原始排列。

2. 康托展开原理详解

2.1 康托展开公式

对于一个排列a₁a₂...aₙ，其康托展开值为：
X = aₙ*(n-1)! + aₙ₋₁*(n-2)! + ... + a₂1! + a₁0!

其中aᵢ表示在aᵢ右侧比aᵢ小的数字的个数。这个展开值是从0开始计数的，所以实际排列序号需要加1。

2.2 逆康托展开过程

给定序号k（从1开始），求对应排列的步骤：

1. k减1得到从0开始计数的值
2. 从最高位开始，用k除以(n-1)!得到商q和余数r
3. 当前位的数字是剩余未使用数字中第q+1小的数字
4. 用r继续计算下一位，直到所有位确定

3. C++实现解析

3.1 预处理阶乘数组

cpp复制int fac[25]={1};
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;

这里我们预计算了1到20的阶乘值，存储在fac数组中。由于N≤20，20!在long long范围内可以表示，所以使用long long类型足够。

3.2 逆康托展开实现

cpp复制void reverse_contor(int x){
    memset(vis,0,sizeof vis);
    x--;
    int j;
    for(int i=1;i<=n;i++){
        int t=x/fac[n-i];
        for(j=1;j<=n;j++){
            if(!vis[j]){
                if(!t) break;
                t--;
            }