跳到主要内容

置换与排列

概述

康托展开求一个排列在全部 n! 个排列中按字典序的排名：第 i 位的贡献等于其后比该位小的数的个数乘以 (n-i) 的阶乘，逐位求和即得名次；用树状数组统计后缀中更小的元素个数，可做到 O(nlogn)。逆康托展开则由给定名次反过来还原出对应排列。给出展开式与倒序枚举、边扫描边用树状数组维护的核心代码，序号从 1 起算故初值取 1。例题为洛谷 P5367 与 UVA11525。

参考资料​

康托展开​

康托展开 求一个排列在全部 n!n! 个排列中按字典序的排名。第 ii 位的贡献为「其后比 aia_i 小的数的个数」乘以 (n−i)!(n-i)!，求和即得名次。用树状数组统计后缀小于个数可做到 O(nlog⁡n)O(n\log n)。逆康托展开则由名次还原出排列。

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。

82 Bcpp
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 取模。

洛谷 UVA11525 Permutation

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