蓝桥杯2022国赛A组
II. 排列距离
康托展开
康托展开可以用来求一个$1\sim n$的任意排列的排名。
什么是排列的排名？
把$1\sim n$的所有排列按字典序排序，这个排列的位次就是它的排名。
时间复杂度
康托展开可以在$O(n^2)$的复杂度内求出一个排列的排名，在用到树状数组优化时可以做到$O(nlogn)$。
实现
因为排列是按字典序排名的，因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同，那么如果这一位如果不相同，就按这一位排序。
比如$4$的排列，$[2,3,1,4]<[2,3,4,1]$，因为在第$3$位出现不同，则$[2,3,1,4]$的排名在$[2,3,4,1]$前面。
示例
我们知道长为$5$的排列$[2,5,3,4,1]$大于以$1$为第一位的任何排列，以$1$为第一位的$5$的排列有$4!$种。这是非常好理解的。但是我们对第二位的$5$而言，它大于第一位与这个排列相同的，而这一位比$5$小的所有排列。不过我们要注意的是，这一位不仅要比$5$小，还要满足没有在当前排列的前面出现过，不然统计就重复了。因此这一位为$1$，$3$或 $4$，第一位为$2$的所有排列都比它要小，数量为$3\times 3!$。
按照这样统计下去，答案就是$1+4!+3\times 3!+2!+1=46$。注意我们统计的是排名，因此最前面要$+1$。
注意到我们每次要用到当前有多少个小于它的数还没有出现，这里用树状数组统计比它小的数出现过的次数就可以了。
康托展开的表达式为：
$X = a_n(n - 1)! + a_{n - 1}(n - 2)! + \cdots + a_1 \cdot 0!$
板子（不加树状数组）：
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int num[1000];
LL fact[1000];
//int fact[] = {1,1,2,6,24,120,720,5040,40320,362880};//定义阶乘表0！ ~ 9！
void getMaxir()//获取0！~n!
{
fact[0] = 1;
for(int i = 1;i<=n;i++){
fact[i] = fact[i-1]*i;
}
}
LL Contor(int *s)//康拓展开
{
LL sum = 0;//记录总的在s之前数目
for(int i = 0;i<n;i++){//枚举固定第i位
int cnt = 0;//记录比第i位小的元素
for(int j = i+1;j<n;j++){//在i后面（剩下未被选择自由元素集合）寻找比第i位小的元素个数
if(s[j]<s[i])cnt++;
}
sum += (fact[n-i-1]*cnt);//累计
}
return sum+1;//返回次序
}
int main()
{
while(scanf("%d",&n)!=EOF){
for(int i = 0;i<n;i++){
scanf("%d",&num[i]);
}
getMaxir();
LL ans = Contor(num);
printf("%lld\n",ans);
}
return 0;
}
板子（树状数组优化）：
#include <iostream>
#include<bits/stdc++.h>
#define mod 998244353
#define lowbit(x) x&(-x)
using namespace std;
typedef long long LL;
const int maxn = 1000000 + 7;
int n,num[maxn],fact[maxn],c[maxn];
void getMaxir()//获取0！~n!
{
fact[0] = 1;
for(int i = 1;i<=n;i++){
fact[i] = (fact[i-1]*i)%mod;
}
}
void Update(int x,int value){
for(int i = x;i<=n;i+=lowbit(i)){
c[i] = (c[i]+value)%mod;
}
}
LL Query(int x){
LL sum = 0;
for(int i = x;i>0;i-=lowbit(i)){
sum = (sum+c[i])%mod;
}
return sum;
}
LL Contor()//康拓展开
{
LL sum = 0;
for(int i = 1;i<=n;i++){
sum = (sum + fact[n-i]*Query(num[i]-1)%mod)%mod;//查询 1~num[i]-1 之间能使用的数字还有几个，累计
Update(num[i],-1); //更新当前数字为已使用状态
}
return (sum+1)%mod;//返回次序
}
int main()
{
scanf("%d",&n);
memset(c,0,sizeof(c));
//获取乘阶项
getMaxir();
//输入排列数组，并初始化树状数组各元素使用次数为1
for(int i = 1;i<=n;i++){
scanf("%d",&num[i]);
Update(i,1);
}
printf("%lld\n",Contor());
return 0;
}
逆康托展开
因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。
如果我们知道一个排列的排名，就可以推出这个排列。因为$4!$是严格大于$3\times 3!+2\times 2!+1\times 1!$的，所以可以认为对于长度为$5$的排列，排名$x$除以$4!$向下取整就是有多少个数小于这个排列的第一位。
示例
同样是上面展开的例子。首先让$46-1=45$，$45$代表着有多少个排列比这个排列小。
$\lfloor\frac {45}{4!}\rfloor=1$，有一个数小于它，所以第一位是$2$。
此时让排名减去$1\times 4!$得到$21$，
$\lfloor\frac {21}{3!}\rfloor=3$，有$3$个数小于它，去掉已经存在的$2$，这一位是$5$。
$21-3\times 3!=3$，
$\lfloor\frac {3}{2!}\rfloor=1$，有一个数小于它，那么这一位就是$3$。
让$3-1\times 2!=1$，有一个数小于它，这一位是剩下来的第二位，$4$，剩下一位就是$1$。即$[2,5,3,4,1]$。
实际上我们得到了形如有两个数小于它这一结论，就知道它是当前第$3$个没有被选上的数，这里也可以用线段树维护，时间复杂度为$O(nlogn)$。
板子（无优化）：
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000 + 7;
int num[maxn];
bool vis[maxn];
int fact[] = {1,1,2,6,24,120,720,5040,40320,362880};//阶乘表0！ ~ 9！
//在n位数字全排列中，第x位的逆康托展开
void DeContor(int n,int x){
x-=1;//初始化全排列数目
for(int i = 1;i <= n;i++){
int k = x/fact[n-i];
x %= fact[n-i];
//查找1-n中未被选择且第k+1小的元素
int sum = 0;
for(int j = 1;j <= n;j++){
if(!vis[j])sum++;
if(sum == k+1){
vis[j] = 1;
num[i-1] = j;
break;
}
}
}
}
int main()
{
int n,index;
while(scanf("%d%d",&n,&index)!=EOF){
memset(vis,0,sizeof(vis));
DeContor(n,index);
for(int i = 0;i < n;i++){
if(i!=0)printf(" ");
printf("%d",num[i]);
}
printf("\n");
}
return 0;
}
题解：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
int tr[20]; // 1 ~ 17
LL fac[20]; // 0! ~ 17!
unordered_map<char, int> alp;
int lowbit(int x){
return x & -x;
}
void update(int u, int v){
for(int i = u; i <= 17; i += lowbit(i))
tr[i] += v;
}
int query(int u){ // [1, u]
int res = 0;
for(int i = u; i >= 1; i -= lowbit(i)) res += tr[i];
return res;
}
void build(){
for(int i = 1; i <= 17; i ++) tr[i] = 0;
for(int i = 1; i <= 17; i ++) update(i, 1);
}
void getfac(){
LL pro = 1;
fac[0] = 1;
for(int i = 1; i <= 17; i ++){
pro = pro * i;
fac[i] = pro;
}
}
LL cantor(string s){
build();
LL cnt = 0; // 多少序列在该序列排名前面
for(int i = 0; i <= 16; i ++){
int t = alp[s[i]];
cnt += query(t - 1) * fac[16 - i];
update(alp[s[i]], -1);
}
return cnt + 1; // 该序列的排名
}
int main(){
string a = "aejcldbhpiogfqnkr";
string b = "ncfjboqiealhkrpgd";
{ // 定义字母映射
alp['a'] = 1, alp['b'] = 2, alp['c'] = 3, alp['d'] = 4, alp['e'] = 5,
alp['f'] = 6, alp['g'] = 7, alp['h'] = 8, alp['i'] = 9, alp['j'] = 10,
alp['k'] = 11, alp['l'] = 12, alp['n'] = 13, alp['o'] = 14, alp['p'] = 15,
alp['q'] = 16, alp['r'] = 17;
}
getfac();
LL rank1 = cantor(a);
LL rank2 = cantor(b);
cout << min(abs(rank1 - rank2), fac[17] - abs(rank1 - rank2));
return 0;
}