康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的（Wiki）
用他可以监视一个排列的状态，减少了 vis 数组的空间开销。
1 /** 2 * Fuck you. 3 * I love you too. 4 */ 5 6 #include7 #define lson i<<2 8 #define rson i<<2|1 9 #define LS l,mid,lson10 #define RS mid+1,r,rson11 #define mem(a,x) memset(a,x,sizeof(a))12 #define gcd(a,b) __gcd(a,b)13 #define ll long long14 #define ull unsigned long long15 #define lowbit(x) (x&-x)16 #define enld endl17 #define mian main18 #define itn int19 #define prinft printf20 21 const double PI = acos (-1.0);22 const int INF = 0x3f3f3f3f;23 const int EXP = 1e-8;24 const int N = 1e5 + 5;25 const int MOD = 1e9 + 7;26 const int MAXN = 1e5 + 5;27 28 using namespace std;29 30 int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320}; //预处理计算康托31 int n;32 string s;33 34 int contor() {35 int sum = 0;36 for (int i = 0; i < n; i++) {37 int cnt = 0;38 for (int j = i + 1; j < n; j++) {39 if (s[i] > s[j]) //计算ai的值40 cnt++;41 }42 sum += cnt * fac[n - i - 1];43 }44 return sum + 1;45 }46 47 int main() {48 while (cin >> n) {49 cin >> s;50 cout << contor() << endl;51 }52 return 0;53 }
双射也就是说，康托可以逆向进行，由X推出原来的那个数。
求 n 位数全排列的第 x 大的排列。
1 /** 2 * Fuck you. 3 * I love you too. 4 */ 5 6 #include7 #define lson i<<2 8 #define rson i<<2|1 9 #define LS l,mid,lson10 #define RS mid+1,r,rson11 #define mem(a,x) memset(a,x,sizeof(a))12 #define gcd(a,b) __gcd(a,b)13 #define ll long long14 #define ull unsigned long long15 #define lowbit(x) (x&-x)16 #define enld endl17 #define mian main18 #define itn int19 #define prinft printf20 21 const double PI = acos (-1.0);22 const int INF = 0x3f3f3f3f;23 const int EXP = 1e-8;24 const int N = 1e5 + 5;25 const int MOD = 1e9 + 7;26 const int MAXN = 1e5 + 5;27 28 using namespace std;29 30 int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320}; //预处理计算康托31 int n, x;32 int vis[10] = { 0};33 string s;34 35 void reverse_contor () {36 int j;37 x--;38 for (int i = 0; i < n; i++) {39 itn r = x / fac[n - i - 1];40 x %= fac[n - i - 1];41 for (j = 1; j <= n; j++)42 if (vis[j] == 0 && r-- == 0)43 break;44 vis[j] = 1;45 s[i] = j + '0';46 }47 }48 49 int main() {50 while (cin >> n >> x) {51 mem(vis,0);52 reverse_contor();53 for(int i=0;i