康拓展开:
把1~n所有排列按照字典序排列,求其中某个排列位次(排名)
逆康托展开:
知道某个全排列的位次(排名),求这个全排列
借鉴OI Wiki https://oi-wiki.org/math/combinatorics/cantor/
稍微改变y总的get_ax函数
int getAx(int x)
{
int k = 1;
while (fact(k) < m) k ++ ;
if (x <= n - k) return x;
memset(st, 0, sizeof st);
//从n - k + 1 到 n 的数进行排列
//逆康托展开
int rank = m - 1;
for (int i = 1; i <= k; i ++ ){
int cur = rank / fact(k - i);
int acc = 0;
for (int j=1; j <= k; j ++ ){
if (!st[j]){
if (acc == cur){
res.push_back(j);
st[j] = true;
break;
}
acc ++;
}
}
rank -= cur * fact(k - i);
}
return res[x - (n - k + 1)] + n - k;
}