康托展开及康托逆展开

题目描述小 G 喜欢玩排列。现在他手头有两个 𝑛 的排列。𝑛 的排列是由 0,1,2,...,𝑛−1这 n 的数字组成的。对于一个排列 𝑝，𝑂𝑟𝑑𝑒𝑟(𝑝) 表示 𝑝 是字典序第 𝑂𝑟𝑑𝑒𝑟(𝑝)小的排列（从 0 开始计数）。对于小于 𝑛! 的非负数 𝑥，𝑃𝑒𝑟𝑚(𝑥) 表示字典序第 𝑥 小的排列。现在，小 G 想求一下他手头两个排列的和。两个排列 𝑝 和 𝑞 的和为 𝑠𝑢𝑚=𝑃𝑒𝑟𝑚((𝑂𝑟𝑑𝑒𝑟(𝑝)+𝑂𝑟𝑑𝑒𝑟(𝑞))%𝑛!)输入输出格式输入格式：输入文件第一行一个数字 n，含义如题。接下来两行，每行 n 个用空格隔开的数字，表示小 G 手头的两个排列。输出格式：输出一行 n 个数字，用空格隔开，表示两个排列的和输入输出样例输入样例#1：1220 131 0输出样例#1：11 0输入样例#2：1321 2 032 1 0输出样例#211 0 2说明1、2、3、4 测试点，1≤𝑛≤10。5、6、7 测试点，1≤𝑛≤5000，保证第二个排列的 𝑂𝑟𝑑𝑒𝑟≤105 。8、9、10 测试点，1≤𝑛≤5000code1#include <cstdio>2#include <cstring>3#include <cmath>4#include <cstdlib>5#include <iostream>6#include <algorithm>7using namespace std;89const 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;1213inline 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}2122int 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();2728 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]++;3435 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 }4142 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}