Skip to main content

置换与排列

参考资料​

康托展开​

x=∑i=1n(n−i)!∑j=in[aj<ai]x=\sum_{i=1}^n(n-i)!\sum_{j=i}^n[a_j<a_i]

序号通常从 11 开始，所以初始令 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 【模板】康托展开

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

Code (1)
#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

求 1∼k1\sim k 的第 nn 个全排列，其中 n=∑i=1kSi×(k−i)!n=\sum_{i=1}^k S_i \times (k-i)!。

Code (1)
#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;
}