Note - 康托展开
1.用途
康托展开可以用来求一个 \(1 \sim n\) 的任意排列的排名。是一个很好的 \(\texttt{hash}\) 方法。
2.算法介绍
时间复杂度
普通的康托展开可以 \(\mathcal{O}(n^2)\) 的复杂度内求出排名，加上树状数组优化后则可以 \(\mathcal{O}(n \log n)\) 。
实现
对于一个排列 \(a\) , 统计 \(a_i\) 后面比它小的数字的个数 \(num\) ，这 \(num\) 表示着有 \(num\) 各数在它前面，而在排列里面，每级别都是阶乘级的，所以答案就累加 \(num × fac_{n-i}\) 。
用数学公式表示就是：
\[\sum_{i=1}^{n-1}fac_{n-i} ×\sum_{j=i+1}^{n} 1 \ (\rm if\ a_j这样的负责度为 \(\mathcal{O}(n^2)\) 。
我们发现后面的 \(\displaystyle\sum_{j=i+1}^{n} 1 \ (\rm if\ a_j
代码
未优化
void contor(int a[]) {
int num = 0, ans = 0;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] < a[i]) {
num++;
}
}
ans += num * fac[n - i];
num = 0;
}
return ans + 1;
}
优化（附树状数组板子）
int c[maxn];
int lowbit(int x) {
return x & -x;
}
void add(int x, int k) {
for (; x <= n; x += lowbit(x)) {
c[x] += k;
}
}
int ask(int x) {
int ans = 0;
for (; x; x -= lowbit(x)) {
ans += c[x];
}
return ans;
}
void contor(int a[]) {
for (int i = 1; i <= n; i++) add(a[i], 1);
int ans = 0;
for (int i = 1; i < n; i++) {
int num = ask(a[i] - 1);
add(a[i], -1);
ans += sum * fac[n - i];
}
return ans + 1;
}
3.逆康托展开
举个例子就很清晰啦~
引用自 康托展开 - OI WIKI
首先让 \(46-1=45\) ，\(45\) 代表着有多少个排列比这个排列小。\(\lfloor \frac{45}{4!} \rfloor=1\)，有一个数小于它，所以第一位是 \(2\)。
此时让排名减去 \(1×4\) 得到 \(21\)，\(\lfloor\frac{21}{3!}\rfloor=3\) ，有 \(3\) 个数小于它，去掉已经存在的 \(2\)，这一位是 \(5\)。
\(21-3×3!=3\) ，\(\lfloor\frac{3}{2!}\rfloor=1\)，有一个数小于它，那么这一位就是 \(3\)。
让 \(3-1×2!=1\) ，有一个数小于它，这一位是剩下来的第二位，\(4\) ，剩下一位就是 \(1\) 。即 \([2,5,3,4,1]\)。
实际上我们得到了形如 有两个数小于它 这一结论，就知道它是当前第 个没有被选上的数，这里也可以用线段树维护，时间复杂度为 \(\mathcal{O}(n \log n)\) 。
\(\bf{Code.}\) (未优化)
bool vis[maxn];
vector reverse_contor(int x) {
x--;
vector ans;
for (int i = 1; i <= n; i++) {
int t = n / fac[i];
for (int j = 1; j <= n; j++) {
if (!vis[j]) {
if (!t) {
vis[j] = true;
ans.push_back(j);
break;
}
t--;
}
}
x %= fac[i];
}
return ans;
}