P3014 [USACO11FEB]牛线Cow Line && 康托展开

康托展开

康托展开为全排列到一个自然数的映射， 空间压缩效率很高。

简单来说， 康托展开就是一个全排列在所有此序列全排列字典序中的第 \(k\) 大， 这个 \(k\) 即是次全排列的康托展开。

康托展开是这样计算的： 对于每一位， 累计除了前面部分， 字典序小于本位的排列总数， 即

LL cantor(){

	LL ans = 0;

	for(LL i = 1;i <= num;i++){

		LL cnt = 0;

		for(LL j = i + 1;j <= num;j++){

			if(ask[j] < ask[i])cnt++;//后方比自己小

			}

		ans += cnt * fac[num - i];//这一位的排列总数

		}

	return ans + 1;

	}

康托逆展开

有康托展开的计算可得， 此映射是可逆的

bool vis[maxn];

void reverse_cantor(LL INDEX){

	memset(vis, 0, sizeof(vis));

	INDEX--;

	LL j;

	for(LL i = 1;i <= num;i++){

		LL t = INDEX / fac[num - i];

		for(j = 1;j <= num;j++){

			if(!vis[j]){

				if(!t)break;

				t--;

				}

			}

		vis[j] = 1;

		printf("%lld ", j);

		INDEX %= fac[num - i];

		}

	puts("");

	}

P3014 [USACO11FEB]牛线Cow Line

题意： 求康托展开和康托逆展开

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

typedef long long LL;

using namespace std;

LL RD(){

    LL out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const LL maxn = 25;

LL num, na;

LL fac[maxn];

void get_fac(){

	fac[0] = 1;

	for(LL i = 1;i <= num;i++)fac[i] = fac[i - 1] * i;

	}

LL ask[maxn];

LL cantor(){

	LL ans = 0;

	for(LL i = 1;i <= num;i++){

		LL cnt = 0;

		for(LL j = i + 1;j <= num;j++){

			if(ask[j] < ask[i])cnt++;

			}

		ans += cnt * fac[num - i];

		}

	return ans + 1;

	}

bool vis[maxn];

void reverse_cantor(LL INDEX){

	memset(vis, 0, sizeof(vis));

	INDEX--;

	LL j;

	for(LL i = 1;i <= num;i++){

		LL t = INDEX / fac[num - i];

		for(j = 1;j <= num;j++){

			if(!vis[j]){

				if(!t)break;

				t--;

				}

			}

		vis[j] = 1;

		printf("%lld ", j);

		INDEX %= fac[num - i];

		}

	puts("");

	}

int main(){

	num = RD();na = RD();

	get_fac();

	char cmd;

	for(LL i = 1;i <= na;i++){

		cin>>cmd;

		if(cmd == 'P')reverse_cantor(RD());

		else{

			for(LL j = 1;j <= num;j++)ask[j] = RD();

			printf("%lld\n", cantor());

			}

		}

	return 0;

	}