#include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std;/* 该题给定一个N,那么在有1.2.3...N个数字的情况下,这些数字高低交替进行排列 把所有符合情况的进行一个字典序排列,问第C个排列是一个怎样的排列 up[i][j]代表长度为i,第一位为j且后面需跟着一个上升数字的方案总数 dn[i][j]代表长度为i,第一位为j且后面需跟着一个下降数字的方案总数 根据我们所定义的状态,我们能够得到一个状态的转移关系(用来状态转移来求解方案数) up[i][j] = SUM{ dn[i-1][k] 且 k >= j } dn[i][j] = SUM( up[i-1][k] 且 k < j ) */ typedef long long int64;int N, path[25], idx; int64 C, up[25][25], dn[25][25];void prep() {up[1][1] = dn[1][1] = 1;for (int i = 2; i <= 20; ++i) {for (int j = 1; j <= i; ++j) { // 枚举长度为i第一位为jfor (int k = 1; k < j; ++k) {dn[i][j] += up[i-1][k];}for (int k = j; k < i; ++k) { // 这个地推需要将后面的数字进行一个映射 // 例如 1,2,3,4,5 假设j=3, 那么还剩下1,2,4,5 比3大的数就只有4,5 那么// 这两个数就可以看做长度为4的情况下的3,4.也就有了[j,i-1]来枚举这个k了up[i][j] += dn[i-1][k];}}} }void dfs(int64 x, int bound, int num, int r) {if (r > 0) { // 要求后面要跟一个上升的数字for (int i = num; i <= bound; ++i) {if (x - dn[bound][i] <= 0) {path[++idx] = i;dfs(x, bound-1, i, -1);break;} else {x -= dn[bound][i];}}}else { // 要求后面跟一个下降的数字for (int i = 1; i < num; ++i) {if (x - up[bound][i] <= 0) {path[++idx] = i; dfs(x, bound-1, i, 1);break;} else {x -= up[bound][i];}}} }void deal(int64 x, int bound) {for (int i = 1; i <= bound; ++i) {if (x - dn[bound][i] <= 0) { // 小于等于0说明在这个数字开始的区域内path[++idx] = i;dfs(x, bound-1, i, -1); // +1或-1表示下一个数字的大小关系break;} else {x -= dn[bound][i]; // 先减去以i开始下降的部分 }if (x - up[bound][i] <= 0) {path[++idx] = i;dfs(x, bound-1, i, 1);break;} else {x -= up[bound][i]; // 再减去以i开始上升的部分 }} }int main() {prep(); // 一个预处理来求出某些常量的组合数 int T;scanf("%d", &T);while (T--) {bool vis[25] = {false};idx = 0;scanf("%d %I64d", &N, &C);deal(C, N);printf("%d", path[1]);vis[path[1]] = true;for (int i = 2; i <= idx; ++i) {int cnt = 0;for (int j = 1; j <= N; ++j) {if (!vis[j]) ++cnt;if (cnt == path[i]) {printf(" %d", j);vis[j] = true;break;}} }puts("");} return 0; }