康托展开

公式

对于一个$n$个数字的全排列$a_0,a_1,a_2,...a_{n-1}$，他的排名为

$lessthen(a_0)*(n-1)! + lessthen(a_1)*(n-2)! + \cdots + lessthen(a_{n-1})0! + 1$

其中$lessthen(a_i)$为$\{1,2,...,n\}-\{a_0,a_1,...,a_i\}$未出现的数字中，小于$x$的数字有多少个

举例：全排列$2,3,1$，它的排名为$1*2!+1*1!+0*0!+1=4$

令$A_i=lessthen(a_i)*(n-i-1)!$

公式可表示为$ans=A_0+A_1+...+A_{n-1}+1$

解析

考虑全排列$\{3,2,1\}$

第一位为$3$，小于$3$且未出现过的数字有$2$个($1$和$2$)，所以有$2*2!$种

第二位为$2$，小于$2$且未出现过的数字有$1$个，因此有$1*1!$种

第三位为$1$，有$0*0!$种

即排名小于$\{3,2,1\}$的全排列有$2\times 2!+1\times 1!=5$种，所以$\{3,2,1\}$的排名为$6$

例题 洛谷P5367

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int maxn = 1e6 + 100;
const ll mod = 998244353;
ll fac[maxn] = {1};
int val[maxn], bit[maxn], n;

void add(int pos, int val){
    for(int i=pos; i<=n; i+=(-i)&i) bit[i] += val;
}

int query(int pos){
    int ret = 0;
    for(int i=pos; i>0; i-=(-i)&i) ret += bit[i];
    return ret;
}

signed main() {
    cin >> n;
    for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % mod;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=1; i<=n; i++) add(i, 1);
    ll ans = 0;
    for(int i=1; i<=n; i++){
        add(val[i], -1);
        ans = (ans + fac[n-i] * query(val[i]) % mod) % mod;
    }
    cout << ans + 1 << endl;
}

逆康托展开

以$\{2,3,4,1\}$为例，$n=4,idx=10$

首先小于它的序列有$idx-1=9$个

1. $9/3!=1......3$，说明对于首位$a_0$，未使用的数字中只有$1$个比它小(此处为$1$)，因此$a_0=2$
2. $3/2!=1......1$，$a_1=3$
3. $1/1!=1......0$，$a_2=4$
4. $0/0!=0$，$a_3=1$

查找未使用数字中的第$k$大可以用线段树/树状数组

例题 UVA11525

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4 + 10;
int tree[maxn * 4], n;

#define mid ((l+r)>>1)
void build(int l, int r, int rt){
    if(l == r) {tree[rt] = 1; return;}
    build(l, mid, rt<<1), build(mid+1, r, rt<<1|1);
    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}

int get(int l, int r, int rank, int rt){
    tree[rt]--;
    if(l == r) return l;
    if(tree[rt<<1] >= rank) return get(l, mid, rank, rt<<1);
    return get(mid+1, r, rank - tree[rt<<1], rt<<1|1);
}

void solve() {
    cin >> n;
    build(1, n, 1);
    for(int i=0, k; i<n; i++){
        cin >> k;
        cout << get(1, n, k + 1, 1) << (i==n-1?'\n':' ');
    }
}

signed main() {
    int t; cin >> t;
    while(t--) solve();
}