数学置换与排列On this page置换与排列Summary参考资料 置换和排列 - OI Wiki 康托展开 - 维基百科 康托展开 康托展开 求一个排列在全部 n!n!n! 个排列中按字典序的排名。第 iii 位的贡献为「其后比 aia_iai 小的数的个数」乘以 (n−i)!(n-i)!(n−i)!，求和即得名次。用树状数组统计后缀小于个数可做到 O(nlogn)O(n\log n)O(nlogn)。逆康托展开则由名次还原出排列。 x=∑i=1n(n−i)!∑j=in[aj<ai]x=\sum_{i=1}^n(n-i)!\sum_{j=i}^n[a_j<a_i]x=i=1∑n(n−i)!j=i∑n[aj<ai] 序号通常从 111 开始，所以初始令 ans=1。 82 Bcppll ans=1;for(int i=n;i>=1;i--){ ans=(ans+fac[n-i]*sum(a[i]))%mod; add(a[i]);} 例题 Problemcode洛谷 P5367 【模板】康托展开求 1∼N1\sim N1∼N 的一个给定全排列在所有 1∼N1\sim N1∼N 全排列中的排名。结果对 998244353998244353998244353 取模。 Problemcode洛谷 UVA11525 Permutation求 1∼k1\sim k1∼k 的第 nnn 个全排列，其中 n=∑i=1kSi×(k−i)!n=\sum_{i=1}^k S_i\times(k-i)!n=∑i=1kSi×(k−i)!。