康托展开

$$x=\sum_{i=1}^n(n-i)!\sum_{j=i}^n[a_j<a_i]$$

参考资料

• 置换和排列 - OI Wiki
• 康托展开 - 维基百科

实现

一般序号从 $1$ 开始，所以初始 ans=1。

ll ans=1;
for(int i=n;i>=1;i--)
{
	ans=(ans+fac[n-i]*sum(a[i]))%mod;
	add(a[i]);
}

例题

洛谷 P5367 【模板】康托展开

洛谷 P5367 【模板】康托展开

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

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=998244353;
const int N=1000005;
int a[N],c[N];
ll fac[N];
void add(int u){while(u<N){c[u]++;u+=u&-u;}}
int sum(int u){int res=0;while(u){res+=c[u];u-=u&-u;}return res;}
void init(){for(int i=0;i<N;i++){fac[i]=i==0?1:fac[i-1]*i%mod;}}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	init();
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	ll ans=1;
	for(int i=n;i>=1;i--)
	{
		ans=(ans+fac[n-i]*sum(a[i]))%mod;
		add(a[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 UVA11525 Permutation

洛谷 UVA11525 Permutation

求 $1\sim k$ 的第 $n$ 个全排列，其中 $n=\sum_{i=1}^k S_i \times (k-i)!$。

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

const int N=50005;
int val[N<<2];
void build(int u,int l,int r)
{
	if(l==r){val[u]=1;return;}
	build(ls,l,mid);
	build(rs,mid+1,r);
	val[u]=val[ls]+val[rs];
}
int query(int u,int l,int r,int v)
{
	val[u]--;
	if(l==r){return l;}
	if(val[ls]<v)return query(rs,mid+1,r,v-val[ls]);
	else return query(ls,l,mid,v);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		build(1,1,n);
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			cout<<query(1,1,n,x+1)<<(i<n?' ':'\n');
		}
	}
	return 0;
}