康托展开

康托展开是一种求一个排列在所有全排列中排名的算法，可以与Hash结合，将一个序列映射为整数
康托展开

先给出康托展开的公式
定义\(0!=1\)，对于一个\(1 \sim n\)的排列\(p=\{p_1, p_2,\cdots,p_n\}\)，其排名

\[r = \sum^{n}_{i=1} a_i(n-i)!\]
其中，\(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)\)

1. const int N = 1e6, P = 998244353;
2. int n, p[N+5];
3. ll fact[N+5]; // 在主函数中预处理阶乘
5. int c[N+5]; // 树状数组
7. void add(int x, int k)
8. {
9.         for (; x <= n; x += lowbit(x))
10.                 c[x] += k;
11. }
13. int query(int x)
14. {
15.         int ans = 0;
16.         for (; x >= 1; x -= lowbit(x))
17.                 ans += c[x];
18.         return ans;
19. }
21. ll cantor(void)
22. {
23.         ll ans = 0;
24.         for (int i = n; i >= 1; i--) {
25.                 int cnt = query(p[i] - 1); // 每次查询[p[i] - 1, 1]的桶的和
26.                 add(p[i], 1);
28.                 ans += cnt * fact[n - i] % P;
29.                 ans %= P;
30.         }
31.         return ans;
32. }

复制代码

逆康拓展开

那么，如何通过一个排列的排名求出这个排列本身呢？
如果我们想求排列的第一项，那么观察上文的公式\(r = \sum_{i=1}^{n} a_i(n-i)!\)
将第一项拆出来，\(r = a_1(n-1)! +\sum_{i=2}^{n}a_i(n-i)!\)
观察第二项，注意到

\[\begin{align*}\sum_{i=2}^{n}a_i(n-i)! &\leq \sum_{i=2}^{n} (n-i) \times (n-i)! \\&= \sum_{i=2}^{n}(n-i+1-1)\times(n-i)! \\&= \sum_{i=2}^{n}(n-i+1)\times(n-i)! - \sum_{i=2}^{n}(n-i)! \\&= \sum_{i=2}^{n}(n-i+1)! - \sum_{i=2}^{n}(n-i)! \\&=(n-1)! - 1\end{align*}\]
因此，\(a_1 = \lfloor \frac{r}{(n-1)!} \rfloor\)，通过枚举，便可求出\(p_i\)
然后，令\(r \leftarrow r \ \text{mod} \  (n-1)!\)，循环求出每一位
朴素算法
[code]bool vis[N+5];vector decantor(ll rk){        vector c;        c.clear();        for (int i = n - 1; i >= 0; i--) {                int cnt = rk / fact;                rk %= fact;                for (int j = 1; j