康托展开_牛客博客

康托展开

什么是康托展开？

就是关于全排列中某个排列的排名的问题

给出一个全排列，求出它是第几个全排列，这就叫康托展开
给出一个全排列的长度以及它的排名，让你求出这个全排列，这叫逆康托展开
（以上全排列都是从 $1 - N$ 的排列，否则需要离散化一下，且排名指从小到大的排名）

康托展开的核心—变进制数

对于一个 $N$ 个数的排列

如果我们依次从左边到右边选择数字组成排列，那么每个位置可以选择的数字个数是确定的。比如第一个数有 $N$ 种选择，第二个数只有 $N - 1$ 种，第三 $. . .$ $, . . .,$ 第 $N$ 个数只有一种选择
如果我们可以把这些选择看做每个位置上的进制，对应的数字就是一个变进制数
那么我们如何得到一个能代表某个全排列的变进制数呢？

以 $N = 5$ 为例，其中一个全排列是 $2, 4, 3, 1, 5$

第一个数只有 $1, 2, 3, 4, 5$ 可以选，所以 $2$ 是排名第二的，将其赋值为1
第二个数只有 $1, 3, 4, 5$ 可以选，所以 $4$ 是排名第三的，将其赋值为2
第三个数只有 $1, 3, 5$ 可以选，所以 $3$ 是排名第二的，将其赋值为1
第四个数只有 $1, 5$ 可以选，所以 $1$ 是排名第一的，将其赋值为0
第五个数只有 $5$ 可以选，所以 $5$ 是排名第一的，将其赋值为0

最后得到的变进制数就是 $12100$

我们看到第 $i$ 位数的值就是 $a_{i}$ 减去左边比它小的数的数量再减去 $1$ (因为 $0$ 也算一个数)

显然我们可以将得到这个数的过程写成一段程序:

//N表示全排列长度
for(int i=1;i<=N;i++) {
    cin>>a[i];
    int x=a[i];
    for(int j=1;j<=a[i];j++) x-=used[j];
    //used[j]表示j是否用过(1用过，0没用）
    used[a[i]]=1;
    a[i]=x-1;
}
//下面给出树状数组加速版(线段树也行啦)
for(int i=1; i<=N; ++i) {
    update(a[i]);//这里先把自己更新了，下面query的时候+1和-1就抵消掉了
    a[i]-=query(a[i]);
}

那它到底代表的排名是多少呢？我们只需要将这个变进制数转化为10进制即可

转化过程：

int ans=0; //其实多数时候需要long long以及取mod
for(int i=1; i<N; ++i) ans=(ans+a[i])*(N-i); //最后的ans+1就是排名，因为要加上0的排名

转化后的答案就是 $39$
这样，整个康托展开过程就结束了！也就几行代码啦。

下面给出完整代码（一道模板题的AC代码）：

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e6+10;
const int mod = 998244353;
const double eps = 1e-9;

int a[maxn], p[maxn], N;
void update(int x){while(x<=N){p[x]++;x+=x&-x;}}
int query(int x){int sum=0;while(x){sum+=p[x];x-=x&-x;}return sum;}

int main() {
	//ios::sync_with_stdio(false);
    N=read();
    for(int i=1; i<=N; ++i) a[i]=read();
    for(int i=1; i<=N; ++i) {
        update(a[i]);
        a[i]-=query(a[i]);
    }
    ll ans=0;
    for(int i=1; i<N; ++i) ans=(ans+a[i])*(N-i)%mod;
    cout<<ans+1<<endl;
}

逆康托展开

就是说你已经知道某全排列的长度以及它的排名，要你求出这个全排列

把这个排名转化为变进制数(细节后续补充)
再用求每位变进制数的逆过程即可求出这个全排列了(细节后续补充)