康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。

康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

对于一个排列 $\{p_n\}$ ，它的排名

ans=\sum_{i=1}^na_i(n-i)!

其中 $a_i$ 表示在当前未出现的元素中的排名。

要求 $a_i$ 的值实际上就是求逆序对个数，可使用树状数组解决。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=1000000+10,mod=998244353;
	ll n,a[N],t[N],mul[N],ans=0;
	ll lb(ll x){return x&-x;}
	void update(ll a)
	{
		while(a<=n) t[a]+=1,a+=lb(a);
		return;
	}
	ll query(ll a)
	{
		ll ret=0;
		while(a>=1) ret+=t[a],a-=lb(a);
		return ret;
	}
	void main()
	{
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++) scanf("%lld",a+i);
		mul[0]=1;
		for(ll i=1;i<=n;i++) mul[i]=mul[i-1]*i%mod;
		for(ll i=n;i>=1;i--)
		{
			ans=(ans+query(a[i])*mul[n-i]%mod)%mod;
			update(a[i]);
		}
		printf("%lld\n",(ans+1)%mod);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

例题

P2518 [HAOI2010]计数

你有一组非零数字（不一定唯一），你可以在其中插入任意个 $0$ ，这样就可以产生无限个数。比如说给定 $\{1,2\}$ ，那么可以生成数字 $12$ ， $21$ ， $102$ ， $120$ ， $201$ ， $210$ ， $1002$ ， $1020$ 等等。

现在给定一个数，问在这个数之前有多少个数（注意这个数不会有前导 $0$ ）。

$n$ 的长度不超过 $50$ ，答案不超过 $2^{63}-1$ 。

点击查看题解

题目中提到不允许 $0$ 作为前导，但恰好提醒解法：

由题意知，一个数字长度是 $n$ ，允许数中的 $0$ 作为前导 $0$ 存在，则直接求当前数字组成的排列，在这 $n$ 位数字全排列中的位次就可以了。题目转化成可重集的康托展开。

原康托展开公式：

ans=\sum_{i=1}^na_ix_i

当变成可重集的排列后， $a_i$ 表示在当前未出现的元素中的排名， $x_i$ 是第 $i$ 位之后各数字组成的可重集全排列方案数。

需要使用杨辉三角求组合数。

实际上本题考查了康托展开的实质。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=50+10;
	char s[N];
	ll a[N],b[N],C[N][N],len,ans=0;
	ll P(ll n)
	{
		ll ret=1;
		for(ll i=0;i<=9;i++)
		{
			ret*=C[n][b[i]];
			n-=b[i];
		}
		return ret;
	}
	void main()
	{
		cin>>s;
		len=strlen(s);
		for(ll i=1;i<=len;i++)
		{
			a[i]=s[i-1]-'0';
			b[a[i]]++;//b 是重数
		}
		C[0][0]=1;
		for(ll i=1;i<=len;i++)
		{
			C[i][0]=C[i][i]=1;
			for(ll j=1;j<=i-1;j++)
				C[i][j]=C[i-1][j-1]+C[i-1][j];
		}
		for(ll i=1;i<=len;i++)
		{
			for(ll j=0;j<=a[i]-1;j++)
			{
				if(b[j]==0) continue;
				b[j]--; ans+=P(len-i); b[j]++;
                //尝试把小于 a_i 的数放在这里，一定形成字典序小于当前的排列
			}
			b[a[i]]--;
		}
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/84de692289e8/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 树状数组逆序对排列组合

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158