康托展开

康托展开

康托展开是一个全排列到自然数的映射。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

公式:

• $a_i$ 表示在位置 $i$ 后面并且小于 $a_i$ 的值的个数。

比如所 $2143$ 的康托展开就是

也就是说这是第 $8$ 个全排列（第一个全排列的康托展开是 $0$）。

int n, m, k;
int a[N] ;//排列
int fac[N] ;//阶乘
int b[N] ;//树状数组
int lowbit(int x){
    return x & -x ;
}
void add(int x, int k){
    while(x <= n){
        b[x] += k ;
        x += lowbit(x) ;
    }
}
int querry(int x){
    int t = 0 ;
    while(x){
        t += b[x] ;
        x -= lowbit(x) ; 
    }
    return t ;
}
void solve(){
    cin >> n ;
    for(int i = 1; i <= n ; ++ i){
        cin >> a[i] ;
    }
    ans = 1 ;
    for(int i = n ; i >= 1; -- i ){//倒着来进行公式
        int num = querry(a[i]) ;
        ans = (ans +  num * fac[n-i] % MOD) % MOD ;
        add(a[i],1) ;
    }
    cout << ans << endl ;

}
signed main(){
    IOS;
    fac[1] = 1 ;
    for(int i = 2; i<= 1e6 ; ++ i){
        fac[i] = fac[i-1] * i % MOD;
    }
    while (T--){
        solve();
    }
    return 0;
}

 

逆康托展开

还以 $7$ 和 $2143$ 为例，

• $\frac{7}{(4-1)!} = \frac{7}{3!} = \frac{7}{6}$，商 $1$ 余 $1$ ，说明在第一位后面只有一个比该为小的数，呢么就说明该位是第 $2$ 小的数，即 $2$ 。
• $\frac{1}{(4-2)!} =\frac{1}{2}$，商 $0$ 余 $1$ ，说明该位置后没有比当前位置还小的数，所以就填当前能填的最小的数，即 $1$ 。
• $\frac{1}{(4-3)!} =\frac{1}{1}$，商 $1$ 余 $0$ ，说明该位置后有一个比当前位置还小的数，，所以就填当前能填的第 $2$ 小的数，即 $4$ 。
• 最后剩下一个数 $3$ 直接填到末尾即可。

int n, m, k;
int a[N] ;
int fac[N] ;
void solve(){
    cin >> n >> k ; //长度和位于排列中的第几个数
    k -- ;
    vector<int> vec ;
    vector<int> res ;
    for(int i = 1 ; i <= n ; ++ i) vec.push_back(i) ;
    for(int i = n ; i > 1; -- i){
        int pos = 0 ;
        if(i-1){
            pos = k / fac[i-1] ;
            k %= fac[i-1] ;
        }
        res.push_back(vec[pos]) ;
        vec.erase(vec.begin() + pos) ;
    }
    res.push_back(vec[0]) ;

    for(auto e : res){
        cout << e << " " ;
    }
    cout << endl ;

}
signed main(){
    IOS;
    fac[1] = 1 ;
    for(int i = 2; i<= 1e6 ; ++ i){
        fac[i] = fac[i-1] * i % MOD;
    }
    while (T--){
        solve();
    }
    return 0;
}