自动搬运

查看原文

来自洛谷，原作者为

	YoungNeal **

搬运于2025-08-24 21:44:24，当前版本为作者最后更新于2018-03-04 11:16:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

上一下原链接 YoungNeal

我们先来科普一下康托展开

定义：

$X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!$

$ai$为整数，并且 $0<=ai<i$ $(1<=i<=n)$

简单点说就是，判断这个数在其各个数字全排列中从小到大排第几位。

比如 $1 3 2$，在1、2、3的全排列中排第2位。

康托展开有啥用呢？

维基： $n$ 位（0~n-1）全排列后，其康托展开唯一且最大约为 $n!$ ，因此可以由更小的空间来储存这些排列。由公式可将 $X$ 逆推出对应的全排列。

它可以应用于哈希表中空间压缩，

而且在搜索某些类型题时，将VIS数组量压缩。比如：八数码，魔板等题 康托展开求法：

比如 $2 1 4 3$ 这个数，求其展开：

从头判断，至尾结束,

① 比 $2$（第一位数）小的数有多少个->$1$个 就是 $1$ ，$1*3!$

② 比 $1$（第二位数）小的数有多少个->$0$个 $0*2!$

③ 比 $4$（第三位数）小的数有多少个->$3$个 就是 $1,2,3$ ，但是 $1,2$ 之前已经出现，所以是 $1*1!$

将所有乘积相加=7

比该数小的数有7个，所以该数排第8的位置。

$1234$ $1243$ $1324$ $1342$ $1423$ $1432$
$2134$ $2143$ $2314$ $2341$ $2413$ $2431$
$3124$ $3142$ $3214$ $3241$ $3412$ $3421$
$4123$ $4132$ $4213$ $4231$ $4312$ $4321$

放一下程序的实现

int contor(int x[]){
    int p=0;
    for(int i=1;i<=n;i++){
        int t=0;
        for(int j=i+1;j<=n;j++){
            if(x[i]>x[j]) t++;
        }
        p+=t*fac[n-i];
    }
    return p+1;
}

康托展开的逆：

康托展开是一个全排列到自然数的双射，可以作为哈希函数。

所以当然也可以求逆运算了。

逆运算的方法：

假设求 $4$ 位数中第 $19$ 个位置的数字。

① 19减去1 → 18

② 18 对 $3!$ 作除法 → 得3余0

③ 0对 $2!$ 作除法 → 得0余0

④ 0对 $1!$ 作除法 → 得0余0

据上面的可知：

我们第一位数（最左面的数），比第一位数小的数有3个，显然 第一位数为→ 4

比第二位数小的数字有0个，所以 第二位数为→1

比第三位数小的数字有0个，因为1已经用过，所以第三位数为→2

第四位数剩下 3

该数字为 $4 1 2 3$ (正解)

再上代码

void reverse_contor(int x){
    memset(vis,0,sizeof vis);
    x--;
    int j;
    for(int i=1;i<=n;i++){
        int t=x/fac[n-i];
        for(j=1;j<=n;j++){
            if(!vis[j]){
                if(!t) break;
                t--;
            }
        }
        printf("%d ",j);
        vis[j]=1;
        x%=fac[n-i];
    }
    puts("");
}

最后上一下本题的代码

#include<cstdio>
#include<cstring>
#include<iostream>
#define int long long
using namespace std;

int fac[25]={1};

int n,k,x;
int val[25];
bool vis[25];

void reverse_contor(int x){
	memset(vis,0,sizeof vis);
	x--;
	int j;
	for(int i=1;i<=n;i++){
		int t=x/fac[n-i];
		for(j=1;j<=n;j++){
			if(!vis[j]){
				if(!t) break;
				t--;
			}
		}
		printf("%d ",j);
		vis[j]=1;
		x%=fac[n-i];
	}
	puts("");
}

int contor(int x[]){
	int p=0;
	for(int i=1;i<=n;i++){
		int t=0;
		for(int j=i+1;j<=n;j++){
			if(x[i]>x[j]) t++;
		}
		p+=t*fac[n-i];
	}
	return p+1;
}

signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
	while(k--){
		char ch;cin>>ch;
		if(ch=='P') scanf("%lld",&x),reverse_contor(x);
		else{
			for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
			printf("%lld\n",contor(val));
		}
	}
	return 0;
}