康托展开

已经连康托展开都快写不出来了......

• 康托展开：求一个排列属于字典序第几大/小排列。
• 逆康托展开：求字典序第几大/小排列。

康托展开：

• 从高到低统计每一位，比如4位的排列，高第一位是3，那么肯定比它小的排列就是这一位是1和2的(1和2必须是没放过的，也就是在3的后面且比3小的)，而且无论放1还是2，后面都可以随便放，是3的阶乘的种放法，所以这一位能确定的小于它的排列数就有(2*3!)个。
• 可以用bit预处理每个数位后面比它小的数的个数(le_i)，然后根据公式(rk=le_n(n-1)!+le_{n-1}(n-2)!+...+le_10!)求出。

code

int contor(vector<int> &per){
	int ans=0;
	int n=per.size();
	for(int i=0;i<n;i++){
		int cnt=0;
		for(int j=i+1;j<n;j++){
			if(per[j]<per[i]){
				cnt++;
			}
		}
		ans+=cnt*fac[n-1-i];
	}
	return ans+1;
}

逆康托展开

• 也是从高到低统计每一位，康托展开是小于它的数乘阶乘，逆康托展开就是除以阶乘，得到小于它的数，然后把序号取模，计算下一位。

code

vector<int> recContor(int n,int k){
	vector<int> ans;
	k--;
	vector<int> vis(n+1,0);
	for(int i=0;i<n;i++){
		int x=k/fac[n-1-i];
		int cnt=0; 
		for(int j=1;j<=n;j++){
			if(!vis[j]){
				if(cnt==x){
					ans.push_back(j);
					vis[j]=1;
				}
				cnt++;
			}
		}
		k%=fac[n-1-i];		
	}
	return ans;
}