康托展开与实例

实例"/>

康托展开与实例

//南昌理工学院ACM集训队

看就完事了

• • 1 康托展开
  • 2 ~~老规矩，上两个样例~~
  • • ① 洛谷的模板题 P5367 【模板】康托展开
    • ② UVA11525 Permutation
  • 3 小结

1 康托展开

康托展开是一个全排列到一个自然数的双射，类似于哈希，每一种排列都有一个唯一的对应字典序排名。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序。

举例
有一个序列[3 4 2 1 5],求这个序列在1~5的全排列中的按字典序的排名。

因为这个序列有5个元素，而且取值范围为1 ~ 5，所以我们不难推断所有的排列组合共有5 * 4 * 3 * 2 * 1种，也就是120种。
因为第一个数可以从5个数里选一个，所以有5种，第二个数能从除了第一个数里选一个，所以第二个数的选择有( 5 - 1 )=4种，以此类推，所有的组合共有5 * 4 * 3 * 2 * 1=120种。

应该小学就会了吧

那么我们用相同的思维去推理[ 3 4 2 1 5 ]在所有的可能的排列里排第几名。
设序列排第n名
第一位是3，在1~5中比3小的有1和2，所以第一个数有两种选择，又因为当第一个数固定时总共有4 * 3 * 2 * 1种选择，所以我们有n = 2 * 4 * 3 * 2 * 1 = 48种选择。
第二位是4，在1~5中比4小的有 1 和 2 和 3，因为第一位已经有3了，所以剩下的选择还有 1 和 2，因为当第二个数固定时总共有3 * 2 * 1种选择，所以我们的n = n + 2 * 3 * 2 * 1 = 60 。
第三位是2，在1~5中比2小的只有1，因为第三个数固定时总共有2 * 1中方案，所以n = n + 1 * 2 * 1 = 62。
第四位是1，在1~5中没有比1小的情况，所以 n = n + 0 。
第五位是5，但是由于它在第五位，所有的数字都被计过一次了，所以 n = n + 0。
当然，我们算的是比当前序列小的所有情况，所以最后n还要再加上1.
所以最后的答案是63，[ 3 4 2 1 5 ]在1~5所有的按字典序排列的序列中排第63位。
那么我们不难看出，计算一个序列的排名是有规律的，而且算出来的名次也是固定的，不会有其它的答案。
公式也很简单
n = 1 + ∑ i = 1 n S i × ( n − i ) ! \Large n=1+\displaystyle\sum_{i=1}^n S\scriptsize i \large × (n-i)! n=1+i=1∑n​Si×(n−i)!
这就是康托展开的公式，我们可以利用这个公式去计算当前排列在所有由小到大全排列中的顺序，也可以根据当前序列的名次，来倒推当前序列的排列，康托展开具有可逆性。

2 老规矩，上两个样例

① 洛谷的模板题 P5367 【模板】康托展开

传送门：P5367 【模板】康托展开

题目描述

求 1∼N 的一个给定全排列在所有 1∼N 全排列中的排名。结果对 998244353 取模。

非常质朴的一道模板题，一看数据，1 ≤ N ≤ 1000000，这数据一看就知道暴力肯定整不出来，那么就要用到我们上面的康托展开的公式了

N = 1 + ∑ i = 1 n S i × ( n − i ) ! \Large N=1+\displaystyle\sum_{i=1}^n S\scriptsize i \large × (n-i)! N=1+i=1∑n​Si×(n−i)!
其中S i 就是比第 i 个数小的数有多少个，n 就是序列有多少个数，那么问题就转化成了求( n - i ) ! 和求S i
( n - i )!只用建立一个数组 d，设 d[0] = 1 ,利用前缀积的思想用后面的乘前面的，循环 n 次即可求出前 n 个数的前缀积。
只用一个循环

d[0]=1;
for (int i = 1; i <= N; i++) d[i] = d[i - 1] * i % mod;//不要忘了取模

那么剩下的问题就是，如何求出比当前数小的而且在之前没有被计算过的数字的个数。

如果直接循环，每个 i 都要循环 i 次，浪费很多时间，所以我们可以用树状数组或线段树等思想维护当前序列，使得每个求S i 的时间复杂度控制在O(log n)内

那么开始 快码加编

建立维护序列所需要的树状数组
不会树状数组点这

打个广告 // ∇ // )○

int lowbit(int x) {return x & -x;
}
void add(int x, int k) {for (int i = x; i <= N; i += lowbit(i)) tr[i] = (tr[i] + k) ;
}
long long sum(int x) {long long res = 0;for (int i = x; i > 0; i -= lowbit(i)) res = (res + tr[i]) % mod;return res;
}

树状数组里维护的是比当前数小的数有多少个，所以输入的时候同时 add(i, 1)，代表当前数的个数 +1 ，在计算答案的时候，将每个计算过的数减去 1 ，即 add(i, -1) 。利用树状数组的时间优势，我们能很快求出每个数所需要的值，最后把输出的答案代入公式中就是最终的答案

ac代码

#include<cstdio>
#define ll long long
const int mod = 998244353;
ll d[1000010];
int tr[4000010],N;
int lowbit(int x) {return x & -x;
}
void add(int x, int k) {for (int i = x; i <= N; i += lowbit(i)) tr[i] = (tr[i] + k) % mod;
}
ll sum(int x) {long long res = 0;for (int i = x; i > 0; i -= lowbit(i)) res = (res + tr[i]) % mod;return res;
}
int main()
{ll  a, ans = 0;scanf("%lld", &N);d[0] = 1;for (int i = 1; i <= N; i++) {d[i] = d[i - 1] * i % mod;add(i, 1);//在计算前缀积的同时建立树状数组，节约时间}for (int i = 1; i <= N; i++) {scanf("%lld", &a);ans = (ans + (sum(a) - 1) * d[N - i]) % mod;//返回的sum是包括a本身的在a之前有多少个数，所以计算结果的时候要减 1add(a, -1);//每个数计算过之后在树状数组中减去这个数}printf("%lld", (ans + 1) % mod);//输出不要忘记答案+1喔ヾ(･ω･`｡)return 0;
}

② UVA11525 Permutation

原题传送门
打不开可以试试下面两个，洛谷的有翻译
洛谷传送门
Virtual Judge传送门

题目的意思是输入 k 和 k 个数据，那些数据经过一个公式的运算得到N，求长度为 k 的字典序排列为 N 的序列。
第一眼看到题目，我马上就开始码求 N 的代码了，但是敲到一半才发现，题目前前后后都没找到取模，再看看k的取值范围 1 ≤ k ≤ 50000，我逐渐开始怀疑我之前的方法…
哼哼，其实这道题虽然是逆康托展开，但是不用求N，因为你仔细看看它给的公式
再看看康托展开的公式

n = 1 + ∑ i = 1 n S i × ( n − i ) ! \Large n=1+\displaystyle\sum_{i=1}^n S\scriptsize i \large × (n-i)! n=1+i=1∑n​Si×(n−i)!
这tm不就是一个公式？
好家伙原来都把 S i 算好了交给我，所以我们只要把第 S i 大的数找出来就可以求出原目标序列的每一位数，所以实质上还是康托展开换了层皮

序列维护方式跟之前大同小异，不过上面的题用过树状数组了，这次我们试试线段树。

不会线段树来这里
再来个广告 // ∇ // )○

struct tree {int l, r, x;
}tr[200001];//保险起见线段树的大小为4*k
void build(int l, int r, int x) {tr[x].l = l; tr[x].r = r;if (l == r) { tr[x].x = 1; return; }else {int mid = (l + r) / 2;build(l, mid, x * 2);build(mid + 1, r, x * 2 + 1);tr[x].x = tr[x * 2].x + tr[x * 2 + 1].x;}
}

利用权值线段树的思想，线段树每一段存的是区间内存在多少个数，当我们访问的时候就可以通过从上到下遍历，找到我们需要的第 S i 大的数，同时我们可以借线段树递归的优势在返回的同时更改每层的权值，达到单点元素修改的目的。

int query(int s, int x) {//查询线段树返回答案int t;if (s == 1 && tr[x].x == 1 && tr[x].l == tr[x].r) {tr[x].x--;return tr[x].l;}if (tr[x * 2].x >= s) {//当当前区间的权值比s小时向左递归，否则向右递归t = query(s, x * 2);}else {s = s - tr[x * 2].x;t = query(s, x * 2 + 1);}tr[x].x--;return t;
}

最后输出每一个query返回的值就是对应的每一位的答案

完整代码

#include<cstdio>
using namespace std;
struct tree {int l, r, x;
}tr[200001];
void build(int l, int r, int x) {tr[x].l = l; tr[x].r = r;if (l == r) { tr[x].x = 1; return; }else {int mid = (l + r) / 2;build(l, mid, x * 2);build(mid + 1, r, x * 2 + 1);tr[x].x = tr[x * 2].x + tr[x * 2 + 1].x;}
}
int query(int s, int x) {int t;if (s == 1 && tr[x].x == 1 && tr[x].l == tr[x].r) {tr[x].x--;return tr[x].l;}if (tr[x * 2].x >= s) {t = query(s, x * 2);}else {s = s - tr[x * 2].x;t = query(s, x * 2 + 1);}tr[x].x--;return t;
}
int main()
{int T, k, s;scanf("%d", &T);while (T--) {scanf("%d", &k);build(1, k, 1);//创建线段树for (int i = 1; i <= k; i++) {scanf("%d", &s);printf("%d", query(s + 1, 1));putchar(i == k ? '\n' : ' ');//按照格式换行或者空格}}return 0;//好习惯
}

3 小结

康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，当遇到类似的题目时可以考虑使用康托展开的公式求出需要的答案
n = 1 + ∑ i = 1 n S i × ( n − i ) ! \Large n=1+\displaystyle\sum_{i=1}^n S\scriptsize i \large × (n-i)! n=1+i=1∑n​Si×(n−i)!

本人小白，如有不对欢迎指正