康托展开 (Cantor expansion)
MiPloRAs_3316
·
·
个人记录
引例
求 1\sim N 的一个给定全排列在所有 1\sim N 全排列中的排名。结果对 998244353 取模。（1\le N\le 1000000）
分析
暴力：直接使用库函数 next_permutation 查找、匹配。时间复杂度大概 O(n!)，十分感人，只能跑过一部分的小样例。
那有没有什么算法能够把复杂度提升到 O(n^2)，甚至 O(n\log n) 呢？
还真有，康托展开！
正确的，是时候引入正题了。
概念
在组合数学中，其解决的是当前排列在全排列中的名次问题。
简单一点就是，当 1\sim n 的所有全排列按字典序排序时，某一个排列 \left\{ a_1, a_2, a_3, \dots, a_n\right \} 在第几位。
本文暂时不考虑哈希相关应用。（其实是我不会）
原理及公式
首先举个例子，手动模拟一下计算过程。
a\left\{5\right\}=\left\{2,4,1,5,3\right\}
- 第一位是 2，比它小的数只有 1，那么只考虑这一位比原序列小时，对答案的贡献时 1\times 4!。
- 第二位是 4，比它小的数有 1,2,3，但 2 已经出现在第 1 位，所以这一位只有放置 1 或 3 时才会比序列 a 小，所以只考虑这一位时，对答案的贡献是 2\times 3!。
- 第三位是 1，没有比它小的数，所以对答案贡献是 0。
- 第四位是 5，比它小的数有 1,2,3,4，其中 1,2,4 已经在前 3 位中出现，所以考虑这一位时，对答案的贡献是 1\times 1!。
- 第五位是 3，比它小的 1,2 已经被使用，所以对答案的贡献是 0\times 0!。
（写了跟写了一样）
然后把上述过程中对答案的贡献加起来，就会得到 Ans=1\times 4!+2\times 3!+0+1\times 1!+0=37，所以比 a\left\{5\right\} 小的排列共有 37 个。那么 a\left\{5\right\} 就排在第 38 位。
为了转化成公式，我们把上述过程整理一下：
然后就可以得出以下公式：
Ans=\sum\limits_{i=1}^{n} \left(\sum_{j=i+1}^{n} \left(a_j<a_i\right) \right) \times (n-i)!
那么按照上述这种朴素的算法，我们可以写出 O(n^2) 的程序（50pts）：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,MOD=998244353;
int a[maxn],n;
long long ans=1,fct[maxn];
void init()
{
fct[0]=1;
for(int i=1; i<=1e6; i++)
fct[i]=(fct[i-1]*i)%MOD;
}
int cantor(int n,int a[])
{
int ans=1;
for(int i=1; i<=n; i++)
{
int cnt=0;
for(int j=i+1; j<=n; j++)
if(a[j]<a[i]) cnt++;
ans=(ans+(cnt*fct[n-i])%MOD)%MOD;
}
return ans%MOD;
}
int main()
{
init();
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
cout<<cantor(n,a);
return 0;
}
进制表示 ？
参考 @yummy 的浅谈康托展开
对于一个全排列，第 i 位有 n-i+1 种选择，如果用变进制数表示，这一位就是 (n-i+1) 进制的。如果这一位选择了第 k 种情况，那么对应的变进制数的这一位就是 k。
为了方便起见，通常以 0 起下标。
以 \left\{2,4,1,5,3\right\} 为例：
- 第一位是 2，是 \left\{1,2,3,4,5\right\} 中的第 2 个，因此变为 1。
- 第二位是 4，是 \left\{1,3,4,5\right\} 中的第 3 个，因此变为 2。
- 第三位是 1，是 \left\{1,3,5\right\} 中的第 1 个，因此变为 0。
- 第四位是 5，是 \left\{3,5\right\} 中的第 2 个，因此变为 1。
- 第五位是 3，是 \left\{3\right\} 中的第 1 个，因此变为 0。
所以用进制来表示就是：(12010)_{unknown}
(12010)_{unknown}=(1\times 4!+2\times 3!+0\times 2+1\times 1!+0\times 0!)_{10}=(36)_{10}
然后转成 10 进制：
树状数组优化
所以考虑使用**树状数组**（单点修改，区间查询）优化。
可以轻松优化成 $O(n\log n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,MOD=998244353;
int a[maxn],n,tree[maxn];
long long fct[maxn];
void init()
{
fct[0]=1;
for(int i=1; i<=1e6; i++)
fct[i]=(fct[i-1]*i)%MOD;
}
int lowbit(int x)
{return x & -x;}
void add(int x,int k)
{
while(x<=n)
tree[x]+=k,\
x+=lowbit(x);
}
int sum(int x)
{
int ans=0;
while(x!=0)
ans=(tree[x]+ans)%MOD,\
x-=lowbit(x);
return ans;
}-
int cantor(int n,int a[])
{
int ans=1;
for(int i=1; i<=n; i++)
{
int cnt=sum(a[i])-1;
ans=(ans+(cnt*fct[n-i])%MOD)%MOD;
add(a[i],-1);
}
return ans%MOD;
}
int main()
{
init();
scanf("%d",&n);
for(int i=1; i<=n; i++)
add(i,1),scanf("%d",&a[i]);
cout<<cantor(n,a);
return 0;
}
```
## 逆康托展开
因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。
如果我们知道一个排列的排名，就可以推出这个排列。
举个例子：求 $5$ 的全排列中排名第 $46$ 位的排列。
首先，$46-1=45$，表示该排列前面有 $45$ 个比它小的排列。
+ $45\div (5-1)!=1\dots 21$，那么对第 $1$ 位而言，有 $1$ 个比它小且没有被使用的数，所以第 $1$ 位是 $2$。
+ $21\div (4-1)!=3\dots 3$，那么对第 $2$ 位而言，有 $3$ 个比它小且没有被使用的数，别忘了还有前面已经用过的 $2$，所以第 $2$ 位是 $5$。
+ $3\div(3-1)!=1\dots 1$，那么对第 $3$ 位而言，有 $1$ 个比它小且没有被使用的数，再算上前两位已经使用的 $2$ 和 $5$，所以第 $3$ 位是 $3$。
+ $1\div(2-1)!=1\dots 0$，那么对第 $4$ 位而言，有 $1$ 个比它小且没有被使用的数，再算上前三位已经使用的 $2,3$ 和 $5$ ，所以第 $4$ 位是 $4$。
+ $0\div(1-1)!=0\dots 0$，那么对第 $5$ 位而言，有 $0$ 个比它小且没有被使用的数，再算上前四位已经使用的 $2,3,4$ 和 $5$ ，所以第 $5$ 位是 $1$。
直接模拟.code $O(n)$：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10,MOD=998244353;
int n,m,ans[maxn],fac[maxn];
bool used[maxn];
void init(int x)
{
fac[0]=1;
for(int i=1; i<=x; i++)
fac[i]=fac[i-1]*i%MOD;
}
inline void reCantor(int rk)
{
rk-=1;
int i=n,j=1;
for(int i=1; i<=n; i++)
{
int tmp=rk/fac[n-i],cnt=0;
rk%=fac[n-i];
for(int j=1; j<=n; j++)
{
cnt+=used[j]^1;
if(cnt==tmp+1)
{
ans[i]=j,used[j]=1;
break;
}
}
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
init(n);
reCantor(m);
for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
return 0;
}
```
~~个人认为上述除法过程类似辗转相除法？~~
## 线段树 逆康托展开
实际上当我们得到了形如 **有 $k$ 个数小于它** 这一结论时，就知道它是当前第 $k+1$ 个 **没有被选上** 的数，这里也可以用线段树维护，时间复杂度为 $O(n\log n)$。
```cpp
#include<bits/stdc++.h>//线段树 逆康托展开
#define int long long
using namespace std;
const int maxn=2e5+10;
int n,rk,tree[maxn<<2],a[maxn],fac[maxn];
void init()
{
fac[0]=1;
for(int i=1; i<=n; i++)
fac[i]=fac[i-1]*i;
}//预处理阶乘
void build (int s, int t, int rt)
{
if(s == t)
{
tree[rt] = 1;
return ;
}
int mid = s + ((t - s) >> 1);
build (s, mid, rt << 1);
build (mid + 1, t, rt << 1 | 1);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}//建树
void update (int x, int s, int t, int rt)
{
tree[rt]--;
if(s == t) return;
int mid = (s + t) >> 1;
if(x <= mid) update(x, s, mid, rt << 1);
else update(x, mid + 1, t, rt << 1 | 1);
}//更新 (编号为 x 的节点值-1)
int sigma (int l, int r, int s, int t, int rt)
{
int sum = 0;
if(l <= s && t <= r)
return tree[rt];
int mid = s + (t - s) >> 1;
if(l <= mid) sum += sigma (l, r, s, mid, rt << 1);
if(r > mid) sum += sigma (l, r, mid + 1, t, rt << 1 | 1);
return sum;
}
inline int find(int s, int t, int rt, int x)
{
if(s == t) return s;
int mid = (s + t) >> 1;
if(x <= tree[rt << 1]) return find(s, mid, rt << 1, x);
else return find(mid + 1, t, rt << 1 | 1, x - tree[rt << 1]);//记得减掉左子树
}//求叶子节点中的第 x 小值
signed main()
{//求 n! 中排名是 m 的全排列
scanf("%lld%lld", &n, &rk);
init();
for(int i=1; i<=n; i++) a[i] = i;
build(1, n, 1);
rk--;
for(int i=1; i<=n; i++)
{
int tmp = rk / fac[n - i];
rk %= fac[n - i];
int ans = find(1, n, 1, tmp + 1);
update(ans, 1, n, 1);
printf("%lld ",ans);
}
return 0;
}
```