康托展开

康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数(1,2,3,4,...,n) ，可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。也就是说，康托展开可以用来求一个 的任意排列的排名。

他的具体原理也不复杂，不过没啥用，不浪费时间展开说明，感兴趣百度有很多优秀的解释。

这里直接给出他的模板代码。暴力O（n^2),树状数组优化可以做到O（nlogn）.但是求排列，一般n不会很大。

所以大部分情况暴力就能解决问题。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll fact[1010],P[1010],A[1010],tree[1010];//P是排列数组，fact是阶乘，自己初始化
ll lowbit(ll x)
{ 
    return x&-x; 
}
ll query(ll x)
{
    ll ans = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        ans += tree[i];
    return ans;
}
void update(ll x, ll d)
{
    for (int i = x; i <1010; i += lowbit(i))
        tree[i] += d;
}
ll cantor(int P[], int n)
{
    ll ans = 1;
    for (int i = n; i >= 1; i--)
    {
        A[i] = query(P[i]);
        update(P[i], 1);
    }
    for (int i = 1; i < n; i++)
        ans = (ans + A[i] * fact[n - i]) % MOD;
    return ans;
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    
    return 0;
}

逆康托展开

其实就是把康托展开的过程反过来，给你排名，让你求出这个排名对应的排列。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll fact[MAXN] = {1}, P[MAXN],A[MAXN]; //fact需要在外部初始化
void decanter(ll x,ll n) //x为排列的排名，n为排列的长度
{
    x--;
    vector<int> rest(n, 0);
    iota(rest.begin(), rest.end(), 1); //将rest初始化为1,2,...,n
    for (int i = 1; i <= n; ++i)
    {
        A[i] = x / fact[n - i];
        x %= fact[n - i];
    }
    for (int i = 1; i <= n; ++i)
    {
        P[i] = rest[A[i]];
        rest.erase(lower_bound(rest.begin(), rest.end(), P[i]));
    }
}