康托展开学习笔记

什么是康托展开

给出一个全排列，求它是第几个全排列，叫做康托展开。

给出全排列长度和它是第几个全排列，求这个全排列，叫做逆康托展开。

如何康托展开

我们看这样一个序列 \([2,5,3,4,1]\)

我们考虑求出比这个序列字典序小的序列个数

首先，以 \(1\) 开头的序列的字典序一定比这个序列小，以 \(1\) 开头的序列一共有 \(4!\) 种

接下来我们发现，以 \(2\) 开头的序列的字典序不一定比它小，我们可以考虑第一位为 \(2\) ，第二位为小于 \(5\) 且不为 \(2\) 的排列

若如此构造，第二位共 \(3\) 种选择，剩下的三位有 \(3!\) 种可能，即第一位最大，剩下的 \(4\) 位共 \(3 \times 3!\) 种选择

同理，前两位最大，剩下的 \(3\) 位共 \(2!\) 种可能

前四位最大，剩下一位只有 \(1!\) 种可能

所以这个序列的排名是 \(1 + 1 \times 4! + 3 \times 3! + 1 \times 2! + 1 \times 1! = 46\)

枚举每一位是 \(O(n)\) ，找未确定的比第 \(i\) 位小的数是 \(O(n)\) ，总时间复杂度是 \(O(n^2)\)?

我们考虑优化，再找比第 \(i\) 位小的数时，我们可以用树状数组优化到 \(O(n \log n)\)

P5367 【模板】康托展开

#include 
typedef long long ll;
using namespace std;
const ll Mod=998244353;
const int N=1e6+7;

ll fac[N];
int a[N];
int c[N];

int n;
ll ans;

inline int lowbit(int x) {
	return x&((~x)+1);
}

inline void update(int pos,int val) {
	for(;pos<=n;pos+=lowbit(pos))
		c[pos]+=val;
}

inline int query(int pos) {
	int sum=0;
	for(;pos;pos-=lowbit(pos))
		sum+=c[pos];
	return sum;
}

signed main() {
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i%Mod; // 预处理阶乘数组
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	for(int i=1;i<=n;++i)
		update(i,1); // 树状数组维护
	for(int i=1;i<=n;++i) {
		ans=(ans+fac[n-i]*query(a[i]-1)%Mod)%Mod; // 统计答案
		update(a[i],-1); // 因为后面考虑的情况中 a[i] 没有贡献，删去
	}
	printf("%lld",ans+1);
    return 0;
}

扩展：逆康托展开

我们考虑这个问题

求长度为 \(5\) ，排名为 \(46\) 的序列是多少

排名为 \(46\) ，就意味着比这个序列小的序列有 \(45\) 个

考虑第一位，因为 \(\left[ \dfrac{46}{4!}\right] = 1\) ，所以当第一位为小于等于 \(1\) 的数时，后 \(4\) 为随便排，都比这个序列小，而当第一位为 \(2\) 时，后买你的书就有了限制，即当第一位为 \(2\) 时，第一位与这个序列的第一位相同，我们就可以确定第一位

接下来让排名减去 \(1 \times 4!\) 得到 \(21\) ， 因为 \(\left[ \dfrac{21}{3!}\right] = 3\) ，且我们已经确定了第一位为 \(2\) ，\(2 \leq 3\)，所以第二位就是剩下的数中第 \(3+1\)? 小的数 \(5\)

同理，让排名减去 \(3 \times 3!\)? 因为 \(\left[ \dfrac{3}{2!}\right] = 1\)? ，所以第三位就是剩下的数中第 \(1+1\)? 小的数 \(3\)??

让排名减去 \(1 \times 2!\)?? 因为 \(\left[ \dfrac{2}{1!}\right] = 1\)?? ，所以第四位就是剩下的数中第 \(1+1\)?? 小的数 \(4\)?

第五位就是剩下来的 \(1\)

所以排名为长度为 \(5\) ，排名为 \(46\) 的序列就是 \([2,5,3,4,1]\)?

至此，我们便完成了逆康托展开

一些例题：

P2524 Uim的情人节礼物·其之弐

P3014 [USACO11FEB]Cow Line S