康托展開是一種求一個排列在所有全排列中排名的算法，可以與Hash結合，將一個排列映射為整數

康托展開

先給出康托展開的公式
定義\(0!=1\)，對于一個\(1 \sim n\)的排列\(p=\{p_1, p_2,\cdots,p_n\}\)，其排名

其中，\(a_i\)是在\(p[i+1, n]\)中比\(p_i\)小的數的個數
舉個例子，\(p=\{2, 5, 3, 4, 1\}\)
那么，在\(2\)之前，有以\(1\)開頭的排列，個數為\(1 \times (5-1)!\)
在\(5\)之前，因為\(2\)已經取過了，所以只剩以\(1, 3, 4\)開頭的排列，個數為\(3 \times (5-2)!\)
..... 以此類推

即枚舉到第\(i\)位時，后面的數形成的排列共有\((n-i)!\)個，而排在這個排列前面的就是第\(i\)位小于\(p_i\)的排列數，即\(a_i(n-i)!\)

所以\(p\)的排名是 \(1 \times (5-1)! + 3 \times (5-2)!+1\times(5-3)!+1\times(5-4)!+0\times(5-5)! = 45\)

所以每次暴力計算\(a_i\)，就可以在\(O(n^2)\)時間計算出展開值

再利用樹狀數組維護桶，并倒序枚舉，就可以優化到\(O(n\lg n)\)

const int N = 1e6, P = 998244353;
int n, p[N+5];
ll fact[N+5]; // 在主函數中預處理階乘

int c[N+5]; // 樹狀數組

void add(int x, int k)
{
	for (; x <= n; x += lowbit(x))
		c[x] += k;
}

int query(int x)
{
	int ans = 0;
	for (; x >= 1; x -= lowbit(x))
		ans += c[x];
	return ans;
}

ll cantor(void)
{
	ll ans = 0;
	for (int i = n; i >= 1; i--) {
		int cnt = query(p[i] - 1); // 每次查詢[p[i] - 1, 1]的桶的和
		add(p[i], 1);

		ans += cnt * fact[n - i] % P;
		ans %= P;
	}
	return ans;
}

逆康拓展開

那么，如何通過一個排列的排名求出這個排列本身呢？
如果我們想求排列的第一項，那么觀察上文的公式\(r = \sum_{i=1}^{n} a_i(n-i)!\)
將第一項拆出來，\(r = a_1(n-1)! +\sum_{i=2}^{n}a_i(n-i)!\)

觀察第二項，注意到

因此，\(a_1 = \lfloor \frac{r}{(n-1)!} \rfloor\)，通過枚舉，便可求出\(p_i\)
然后，令\(r \leftarrow r \ \text{mod} \ (n-1)!\)，循環求出每一位

樸素算法

bool vis[N+5];
vector<int> decantor(ll rk)
{
	vector<int> c;
	c.clear();

	for (int i = n - 1; i >= 0; i--) {
		int cnt = rk / fact[i];
		rk %= fact[i];

		for (int j = 1; j <= n; j++) {
			if (!vis[j]) {
				if (!cnt) {
					c.push_back(j);
					vis[j] = 1;
					break;
				}
				cnt--;
			}
		}
	}
	return c;
}

例題
P5367 【模板】康托展開
CF501D Misha and Permutations Summation