康托展开及其逆展开

康托展开

可以用于求 全排列 的排名（字典序）。

我们先给定一组排列。这里为了举例方便就拿了 OI-wiki 上的例子 \(\{2,5,3,4,1\}\) 了。

我们第一位是 \(2\) ，那么以 \(1\) 开头的就都比它小。后面的也是同理的搞法，就是看当前这位有多少个比它小还之前没有出现过的数（因为要保证是排列）。由于高位上的以及统计过了，我们只需要统计当前位下的即可。具体来说，多少个比它小还之前没有出现过的数的个数乘上目前长度 \(-1\) 的阶乘就是比它小的排列个数。

我们每位如此统计完加起来，然后再 \(+1\) （因为是排名）即可。这个过程我们用树状数组维护，复杂度 \(O(n\log n)\)。

逆康托展开

其实我们得知一个排列的排名后也可以得到其原本的排列。

我们先对于排名自减一次。然后我们每次对于长度 \(-1\) 的阶乘做除法，得到余数 \(r\) 和除数 \(x\) ，那么这一位上的数就应该是之前没出现过的数中的第 \(x+1\) 名，找到它并且把排名赋值为 \(r\) 进入子问题。

一直做长度次即可。这个过程我们用权值线段树维护可以做到 \(O(n\log n)\)。

总的参考代码：

#include
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
	inline bool blank(const char &c){
		return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
	}
	inline void gs(char *s){
		char ch=gc();
		while(blank(ch) ) {ch=gc();}
		while(!blank(ch) ) {*s++=ch;ch=gc();}
		*s=0;
	}
	inline void gs(std::string &s){
		char ch=gc();s+='#';
		while(blank(ch) ) {ch=gc();}
		while(!blank(ch) ) {s+=ch;ch=gc();}
	}
	inline void ps(char *s){
		while(*s!=0) pc(*s++);
	}
	inline void ps(const std::string &s){
		for(auto it:s) 
			if(it!='#') pc(it);
	}
	template
	inline void read(T &s){
		s=0;char ch=gc();bool f=0;
		while(ch<'0'||'9'
	inline void read(T &s,A &...a){
		read(s);read(a...);
	}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=1e6+3,mods=998244353;
inline int inc(int x,int y){
	return (x+=y)>=mods?x-mods:x;
}
inline int dec(int x,int y){
	return (x-=y)<0?x+mods:x;
}
inline int mul(int x,int y){
	return 1ll*x*y%mods;
}
int n;
struct BitTree{
	int c[N];
	inline void add(int x,int k){
		for(;x<=n;x+=(x&-x) ) c[x]+=k;
	}
	inline int find(int y){
		int res=0;
		for(;y;y-=(y&-y) ) res=inc(res,c[y]);
		return res;
	}
}t1;
struct SegTree{
	struct node{
		int l,r,mid;
		int cnt;
	}t[N<<2];
	inline void pushup(int i){
		t[i].cnt=t[i<<1].cnt+t[i<<1|1].cnt;
	}
	inline void build(int i,int l,int r){
		t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1;
		t[i].cnt=1;
		if(l==r){
			return;
		}	
		build(i<<1,l,t[i].mid);
		build(i<<1|1,t[i].mid+1,r);
		pushup(i);
	}
	inline int kth(int i,int k){
		if(t[i].l==t[i].r){
			if(k!=1) return -1;
			return t[i].l;
		}
		int key=t[i<<1].cnt;
		if(key>=k) return kth(i<<1,k);
		return kth(i<<1|1,k-key);
	}
	inline void modify(int i,int p,int k){
		if(p<=t[i].l and t[i].r<=p){
			t[i].cnt+=k;
			return;
		}
		if(p<=t[i].mid) modify(i<<1,p,k);
		if(t[i].mid+1<=p) modify(i<<1|1,p,k);
		pushup(i);
	}
}t2;
int fac[N];
inline int Contor(int *a){
	memset(t1.c,0,sizeof(t1.c) );
	int rk=0;
	for(int i=1;i<=n;++i){
		t1.add(a[i],1);
		rk=inc(rk,mul(dec(a[i],t1.find(a[i]) ),fac[n-i]) );
	}
	return rk+1;
}
inline void InvContor(int x,int *a){
	t2.build(1,1,n);--x;
	for(int i=1;i<=n;++i){
		int r=x/fac[n-i];
		x%=fac[n-i];
		a[i]=t2.kth(1,r+1);
		t2.modify(1,a[i],-1);
	}
}
int a[N],b[N];
int main(){
	filein(a);fileot(a);
	read(n);
	fac[0]=fac[1]=1;
	for(int i=2;i<=n;++i){
		fac[i]=mul(fac[i-1],i);
	}
	for(int i=1;i<=n;++i){
		read(a[i]);
	}
	int rk=Contor(a);
	printf("%d\n",rk);
	InvContor(rk,b);
	for(int i=1;i<=n;++i){
		printf("%d ",b[i]);
	}pc('\n');
	return 0;
}