康托展开
康托展开是一种求一个排列在所有全排列中排名的算法，可以与Hash结合，将一个序列映射为整数康托展开
先给出康托展开的公式
定义\(0!=1\)，对于一个\(1 \sim n\)的排列\(p=\{p_1, p_2,\cdots,p_n\}\)，其排名
\
其中，\(a_i\)是在\(p\)中比\(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;
ll fact; // 在主函数中预处理阶乘
int c; // 树状数组
void add(int x, int k)
{
for (; x <= n; x += lowbit(x))
c += k;
}
int query(int x)
{
int ans = 0;
for (; x >= 1; x -= lowbit(x))
ans += c;
return ans;
}
ll cantor(void)
{
ll ans = 0;
for (int i = n; i >= 1; i--) {
int cnt = query(p - 1); // 每次查询 - 1, 1]的桶的和
add(p, 1);
ans += cnt * fact % 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)!\)
观察第二项，注意到
\[\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)!\)，循环求出每一位
朴素算法
bool vis;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
页:
[1]