康托展开与逆康托展开算法模板

const int N =21;
ll fac[N];
void init(){
	fac[0] = 1;
	for (int i =1; i < 21; i++) {
		fac[i] = fac[i - 1] * i;
	}
}
ll contor(int n,int s[]) {
	ll rnk = 0, cnt;
	for (int i = 0; i < n; i++) {
		cnt = 0;
		for (int j = i + 1; j < n; j++){
			if (s[i] > s[j])cnt++;
		}
		rnk += cnt * fac[n - i - 1];
	}
	return rnk + 1;//如果排名从1开始
}
//n为数列元素个数，rnk为排名，s为计算出的排列
void revcontor(int n, ll rnk, int s[]) {
	rnk--;
	bool vis[21] = {0};
	ll t; int j;
	for (int i = 0; i < n; i++) {
		t=rnk/fac[n-i-1];
		for (j = 1; j <=n; j++) {
			if (!vis[j]) {
				if (t == 0)break;
				t--;
			}
		}
		s[i] =j;
		vis[j] = 1;
		rnk %= fac[n - i - 1];
	}
}