康托展开

康托展开

题目描述

输入两个自然数m，n期中1<=n<20,1<=m<=n! 输出给定的排列在n个数全排列中按小到大第几个出现？ 输出n个数全排列中第m种全排列。

输入

第一行两个整数n，m； 接下来一行n个数，n个数的一种排列。

输出

第一行一个整数，表示给定排列是全排列中第几个。 第二行输出n个数全排列中第m个全排列。每两个数之间空一格。

样例输入

3 2 1 2 3

样例输出

1 1 3 2

求康拓展开，和逆康托展开

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<iomanip> using namespace std; #define ll long long ll n,m,a[30]; bool book[30]; int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ll f[30];f[1]=1; for(ll i=2;i<=n;i++)f[i]=f[i-1]*i; long long ans=0; for(int i=1;i<=n;i++) { int temp=0; for(int j=i+1;j<=n;j++) if(a[i]>a[j])temp++; ans+=temp*f[n-i]; } printf("%lld\n",ans+1);bool flag=0;m--; for(int i=n-1;i>=0;i--) { ll p=m/f[i],tot=0; for(int j=1;j<=n;j++) { if(!book[j])tot++; if(tot==p+1){tot=j;break;} } if(flag)putchar(' '); printf("%lld",tot); flag=true;book[tot]=true;m%=f[i]; }puts(""); return 0; }