Problem Description

A sequence of length n is called a permutation if and only if it's composed of the first n positive integers and each number appears exactly once.

Here we define the "difference sequence" of a permutation p1,p2,…,pn as p2?p1,p3?p2,…,pn?pn?1. In other words, the length of the difference sequence is n?1 and the i-th term is pi+1?pi

Now, you are given two integers N,K. Please find the permutation with length N such that the difference sequence of which is the K-th lexicographically smallest among all difference sequences of all permutations of length N.

Input

The first line contains one integer T indicating that there are T tests.

Each test consists of two integers N,K in a single line.

* 1≤T≤40

* 2≤N≤20

* 1≤K≤min(104,N!)

Output

For each test, please output N integers in a single line. Those N integers represent a permutation of 1 to N, and its difference sequence is the K-th lexicographically smallest.

Sample Input

7
3 1
3 2
3 3
3 4
3 5
3 6
20 10000

Sample Output

3 1 2
3 2 1
2 1 3
2 3 1
1 2 3
1 3 2
20 1 2 3 4 5 6 7 8 9 10 11 13 19 18 14 16 15 17 12

題意：t 組數據，每組給出 n、k 兩個數，定義差異排列為 ，求 n 的全排列，求出?n 的所有全排列中差異序列字典序第 k 小的排列

思路：

k 的范圍是 1 到?min(1E4,n!)，而 n 最大是 20，當 n=8 時，n!=40320，因此 k 最大是 1E4

故而對 n 分情況討論：

• n<=8 時：直接求出所有差異序列的全排列，然后 sort 排序后輸出即可
• n>=9?時：第一位直接取 n，然后再取剩下的?n-1 位的全排列，到 k 為止即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<unordered_map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;} LL quickPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;} LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); } LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); } LL LCM(LL x,LL y){ return x/GCD(x,y)*y; } const double EPS = 1E-10; const int MOD = 998244353; const int N = 10000+5; const int dx[] = {-1,1,0,0,1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct Node {int pos[22], p[22]; } node[50005]; int n,k; bool cmp(Node x, Node y) {for (int i = 1; i < n; i++) {if (x.p[i] != y.p[i])return x.p[i] < y.p[i];} } int a[25]; int main() {int t;scanf("%d", &t);while (t--) {scanf("%d%d", &n, &k);if (n <= 8) { // n<=8時for (int i = 1; i <= n; i++)a[i] = i;for (int i = 1; i <= n; i++)//記錄位置node[1].pos[i] = a[i];for (int i = 2; i <= n; i++)//求差異排列node[1].p[i - 1] = a[i] - a[i - 1];int num = 2;while (next_permutation(a + 1, a + 1 + n)) {//生成全排列for (int i = 1; i <= n; i++)node[num].pos[i] = a[i];for (int i = 2; i <= n; i++)node[num].p[i - 1] = a[i] - a[i - 1];num++;}sort(node + 1, node + num, cmp);for (int i = 1; i <= n - 1; i++)printf("%d ", node[k].pos[i]);printf("%d\n", node[k].pos[n]);} else { // n>=9時printf("%d ",n); //第一位一定是nfor(int i=1;i<=n-1;i++) //剩余的n-1位a[i]=i;if (k == 1) { //特判k=1for(int i=1;i<=n-2;i++)printf("%d ",a[i]);printf("%d\n",a[n-1]);}else{int num = 1;while (next_permutation(a + 1, a + 1 + (n - 1))) { //輸出前k個num++;if (num == k) {for (int i = 1; i <= n - 2; i++)printf("%d ", a[i]);printf("%d\n", a[n - 1]);break;}}}}}return 0; }

?

總結

以上是生活随笔為你收集整理的permutation 1（HDU-6628）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。