康托展开（Cantor Expansion）

概述及流程

利用康托展开，我们可以求出一个排列在全排列中的排名，一个排列的康托展开是它的前述排名-1。因此，康托展开是一个排列到自然数的双射，具有双向的唯一映射关系。
我们令康托展开的结果为$X$，对于排列$A_i$，有展开式
$$ X = a_1(n-1)! + a_2(n-2)! + \cdots + a_n \cdot 0! $$
展开式中的$a_i$代表，在$A_1$到$A_i$中没出现过的，不大于$A_i$的$[1, n]$中的数的数量。下面我们用一个例子来说明。
排列1 2 4 3 5的康托展开是$X=2$，展开式为
$$ X = 0 \cdot 4! + 0 \cdot 3! + 1 \cdot 2! + 0 \cdot 1! + 0 \cdot 0! $$
$A_1=1$之前没出现过的不大于1的数不存在，因此$a_1=0$，而$A_3=4$之前有1个没出现过的数3，因此$a_3=1$。

算法实现

// Code by KSkun, 2018/7
LL res = 0;
for(int i = 1; i <= n; i++) {
    int cnt = 0;
    for(int j = 1; j <= i; j++) {
        if(a[j] <= a[i]) cnt++;
    }
    res += mul[n - i] * (a[i] - cnt);
}

注：代码中$mul[i]=i!$。

康托展开的逆运算

概述及流程

通过逆运算，我们可以把一个康托展开后的值还原成对应的排列。我们只需要逆着做上述过程就好。例如，我们知道了大小为5的排列的值$X=4$，现在将其展开。
我们先确定第一位，求出$a_1=\frac{X}{4!}=0$，因此要从前面没出现过的数中找到第1个数填入，即$A_1=1$。然后将$X$变为$X \bmod 4!=4$。
类似地，$A_2=2$。
到第三位的时候，$a_3=\frac{X}{2!}=2$，意义是从前面没出现过的数中找到第3个，即$A_3=5$。
接着做完整个流程，得到了排列1 2 5 3 4。

算法实现

// Code by KSkun, 2018/7
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) {
    LL num = res / mul[n - i];
    res %= mul[n - i];
    for(int j = 1; j <= n; j++) {
        if(!vis[j]) {
            if(!num) {
                a[i] = j; vis[j] = true; break;
            }
            num--;
        }
    }
}

例题：[USACO11FEB]牛线Cow Line

题意简述

查询一个排列在全排列中的排名，及给排名求排列。

题解思路

直接实现康托展开和逆康托展开即可。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline char readop() {
    char c;
    while(!isupper(c = fgc())) {}
    return c;
}

const int MAXN = 25;

int n, k, a[MAXN];
bool vis[MAXN];
LL mul[MAXN];

int main() {
    mul[0] = mul[1] = 1;
    for(int i = 2; i <= 20; i++) {
        mul[i] = mul[i - 1] * i;
    }
    n = readint(); k = readint();
    while(k--) {
        char op = readop();
        if(op == 'P') {
            memset(vis, 0, sizeof(vis));
            LL res = readint() - 1;
            for(int i = 1; i <= n; i++) {
                LL num = res / mul[n - i];
                res %= mul[n - i];
                for(int j = 1; j <= n; j++) {
                    if(!vis[j]) {
                        if(!num) {
                            printf("%d ", j); vis[j] = true; break;
                        }
                        num--;
                    }
                }
            }
            puts("");
        } else {
            LL res = 0;
            for(int i = 1; i <= n; i++) {
                a[i] = readint();
            }
            for(int i = 1; i <= n; i++) {
                int cnt = 0;
                for(int j = 1; j <= i; j++) {
                    if(a[j] <= a[i]) cnt++;
                }
                res += mul[n - i] * (a[i] - cnt);
            }
            printf("%lld\n", res + 1);
        }
    }
    return 0;
}

参考资料

• 康托展开 – 维基百科，自由的百科全书
• P3014 [USACO11FEB]牛线Cow Line 题解