康托展开及康托逆展开
题目描述
小 G 喜欢玩排列。现在他手头有两个 的排列。 的排列是由 这 n 的数字组成的。对于一个排列 ， 表示 是字典序第 小的
排列（从 0 开始计数）。对于小于 的非负数 ， 表示字典序第 小的排列。
现在，小 G 想求一下他手头两个排列的和。两个排列 和 的和为
输入输出格式
输入格式：
输入文件第一行一个数字 n，含义如题。
接下来两行，每行 n 个用空格隔开的数字，表示小 G 手头的两个排列。
输出格式：
输出一行 n 个数字，用空格隔开，表示两个排列的和
输入输出样例
输入样例#1：
12
20 1
31 0
输出样例#1：
11 0
输入样例#2：
13
21 2 0
32 1 0
输出样例#2
11 0 2
说明
1、2、3、4 测试点，。
5、6、7 测试点，，保证第二个排列的 。
8、9、10 测试点，
code
1#include <cstdio>
2#include <cstring>
3#include <cmath>
4#include <cstdlib>
5#include <iostream>
6#include <algorithm>
7using namespace std;
8
9const int max_n = 5e4 + 10;
10int cnt[max_n], p1[max_n], p2[max_n], pp1[max_n], pp2[max_n], ans[max_n];
11int n;
12
13inline int getnum()
14{
15 int ans = 0; char c; bool flag = false;
16 while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
17 if (c == '-') flag = true; else ans = c - '0';
18 while (isdigit(c = getchar())) ans = ans * 10 + c - '0';
19 return ans * (flag ? -1 : 1);
20}
21
22int main()
23{
24 n = getnum();
25 for (int i = n; i >= 1; i--) p1[i] = getnum();
26 for (int i = n; i >= 1; i--) p2[i] = getnum();
27
28 for (int i = 1; i <= n; i++)
29 for (int j = 1; j < i; j++)
30 if (p1[j] < p1[i]) pp1[i]++;
31 for (int i = 1; i <= n; i++)
32 for (int j = 1; j < i; j++)
33 if (p2[j] < p2[i]) pp2[i]++;
34
35 for (int i = 2; i <= n; i++)
36 {
37 ans[i] += pp1[i] + pp2[i];
38 ans[i + 1] += ans[i] / i;
39 ans[i] %= i;
40 }
41
42 for (int i = n; i >= 1; i--)
43 {
44 int _ = -1;
45 while (ans[i] >= 0)
46 {
47 _++;
48 if (!cnt[_]) ans[i]--;
49 }
50 printf("%d ", _);
51 cnt[_] = 1;
52 }
53}
康拓展开：
1const int PermSize = 12;
2long long factory[PermSize] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };
3long long Cantor(string buf) {
4 int i, j, counted;
5 long long result = 0;
6 for (i = 0; i<PermSize; ++i) {
7 counted = 0;
8 for (j = i + 1; j<PermSize; ++j){
9 if (buf[i]>buf[j])++counted;
10 }
11 result = result + counted*factory[PermSize - i - 1];
12 }
13 return result;
14}
康托逆展开：
1/*返回由前n个数[1, n]组成的全排列中第m大的排列。*/
2vector<int> deCantor(int n, int m) {
3 vector<int> res;
4 long long buf = 0;
5 m--;
6 for(int f = 0; n > 0; n--) {
7 f = m / facts[n - 1];
8 m = m % facts[n - 1];
9 while(buf & (1 << (f + 1)))f++;
10 res.push_back(f + 1);
11 buf |= (1 << (f + 1));
12 }
13 return res;
14}