（1377.编码II）题解空间压缩神器——康拓展开模板

题目大意：

输入一个排列(长度小于50),输出它是第几个排列! 第一个排列为0

分析：

求这个排列是第几个，我们先要学一个叫康拓展开的东西

康拓展开定义：

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的名次，因此是可逆的。

另外康托展开解决的是当前序列在全排序的名次的问题，也就是问题所求。

康拓展开公式：

X=a[n](n-1)!+a[n-1](n-2)!+a[n-2]*(n-3)!+…+a[1]*0!

其中a[n]表示当前数是数列中未出现的数中第几小的【注意从0开始计数】

举个例子：

对于序列3,2,5,4,1

对于3:比3小的有1、2，所以3是第2小的，X+=2?(5?1)!

对于2:比2小的有1,所以2是第1小的，X+=1?(4?1)!

对于5:比5小的有1、2、3、4，但由于2、3已经出现过了，所以目前5是第2小的，X+=2*(3-1)!

对于4:比4小的只剩1，所以X+=1*(2-1)!

对于1:已经是最小的，X+=0*(1-1)!

放个模板

//为了节省时间，我们先预处理阶乘：
void cal(){
	fac[0]=1;
	for(int i=1;i<=9;i++) fac[i]=fac[i-1]*i;
}

//然后就是康拓展开：
int kangtuo(int* a){
	int ans=0;
	for(int i=0;i<=n;i++) label[i]=1;
	for(int i=0;i<n;i++){
		int cnt=0;
		for(int j=0;j<a[i];j++) if(label[j]) cnt++;
		label[a[i]]=0;
		ans+=cnt*fac[n-i-1];
	}
	return ans;
}

学会了康拓展开，做这道题就很容易了。但是当你自信套模板时，你发现你的程序居然WA了

这是为什么呢，我们发现题目中排列(长度小于50)，如果算50！的话，unsigend long long也存不下

这时我们就需要用到高精度了

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=10001;// 用常数存起来避免出错 
int n,ll,k,x[MAXN];
int a[MAXN],d[MAXN],kk[MAXN];
int c[MAXN][MAXN];
char str1[10001];
void mul(int x,int a[])//高精乘 
{
	int g=0;
	for(int i=MAXN-1;i>0;i--)
		{
			a[i]=a[i]*x+g;
			g=a[i]/10;
			a[i]%=10;
		}
}
void add(int a[])//高精加 
{
	long long g=0;
	for (long long i=MAXN-1;i>0;i--)
		{
			x[i]=x[i]+a[i]+g;
			g=x[i]/10;
			x[i]%=10; 
		}
}
void init()
{
	gets(str1);//毒瘤的输入，我调了好久 
	n=1;
	for (int i=0;i<strlen(str1);i++)
	{
		if (str1[i]>='0'&&str1[i]<='9')
			a[n]=a[n]*10+str1[i]-'0';
		if (str1[i]==' ')
			n++;
	}
	c[0][MAXN-1]=1;
	for (int i=1;i<=n+1;i++)//预处理阶乘 
	{
		memset(d,0,sizeof(d));
		memcpy(d,c[i-1],sizeof(c[i-1]));
		mul(i,d);
		memcpy(c[i],d,sizeof(d));
	}
	x[MAXN-1]=1; 
}
void work()
{
	for (int i=1;i<=n;i++)//康拓展开模板 
	{
		ll=a[i];
		k=0;
		for (int j=i+1;j<=n;j++)
			if (a[j]<ll)
				k++;
		memcpy(kk,c[n-i],sizeof(c[n-i]));
		mul(k,kk);
		add(kk);
		
	}
}
void putout()//输出 
{
	int i=0;
	while (x[i]==0&&i<MAXN-1)
		i++;
	for (int j=i;j<MAXN;j++)
		cout<<x[j];
}
int main()
{
	init();
	work();
	putout();
    return 0;	
 }

拓展：

康托逆展开：

康托逆展开就是知道排名，求出当前数列

首先，把排名转化为以0为开始的排名【就是自减1】

举个例子吧：

对于1,2,3,4,5，求第10的数列

10-1=9

第一个数：9/(5-1)!=0…9,所以第一个数是当前未出现的第0个数：1

第二个数：9/(4-1)!=1…3,所以第二个数是当前未出现的第1个数：3

第三个数：3/(3-1)!=1…1,所以第二个数是当前未出现的第1个数：4

第四个数：1/(2-1)!=1…0,所以第二个数是当前未出现的第1个数：5

第五个数：0/(1-1)!=0…0,所以第二个数是当前未出现的第0个数：2

就这样，第十数列就是1,3,4,5,2

CODE:

void codel(int x){
	int cnt;
	for(int i=0;i<m;i++) label[i]=1;
	for(int i=0;i<m;i++){
		cnt=x/fac[m-1-i];
		x=x%fac[m-1-i];
		for(int j=0;j<m;j++){
			if(!label[j]) continue;
			if(!cnt) {label[j]=0;n[i]=j;break;}
			cnt--;
		}
	}
}