题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6628

题目：

permutation 1

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

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(10^4,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

 

 解题思路：

n，1,开头的排列对应的difference的第一个数字是最小的=1-n， 8！=40320， 9！=362880，而k最大只取10000。

对于长度为9的排列，当前两位n，1固定，那么后面的7位共有7！=5040种方案，若第一位n固定，后面的8位由8！>10000种方案，可知对于长度>=9的排列，只需在n,1,2,...,n-1这个字典序的基础上再排列min(k,10000)-1次即可求得答案

对于长度≤8的排列，预处理。排列长度一定时，将每个排列对应difference序列转化为char[],sort一下即可，用结构体存数据，询问时根据n,k直接输出。

时间复杂度：预处理O(46232)+T*(10000) = e5

 

ac代码：

13ms跑完！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=40325;// 8！=40320！！不是10000
int n, k;
struct node{
    int num[12];
    char c[12];
    friend bool operator < (node a, node b)
    {
        return strcmp(a.c, b.c) < 0;
    }
}a[12][maxn];//a[i][j],i：排列长度 j：字典序第j小的difference排列
int b[25] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,};
int ans[30];
void prepare()//预处理n <= 8
{
    for(int i = 2; i <= 8; i++)//枚举排列长度
    {
        int cnt = 1;
        do{
           for(int j = 1; j <= i; j++) //确定这个排列的num【】和c【】
           {
               a[i][cnt].num[j] = b[j];//b从1开始存
               if(j > 1) a[i][cnt].c[j - 2] = b[j] - b[j - 1] + 'a';//c从0开始存，方便排序
           }
           a[i][cnt].c[i - 1] = '\0'; //!!!
           cnt++;
        }while(next_permutation(b+1, b+1+i));
        sort(a[i] + 1, a[i] + cnt);//排名从1开始
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int n, k, t;
    scanf("%d", &t);
    prepare();
    while(t--)
    {
        scanf("%d %d", &n, &k);
        k = min(k, 10000);
        if(n > 8)
        {
            ans[1] = n;
            for(int i = 2; i <= n; i++)
                ans[i] = i - 1;//字典序最小的排列已经得出
            for(int i = 1; i < k; i++) // 还需排k-1次
                next_permutation(ans + 1, ans + 1 + n);
            for(int i = 1; i <= n; i++)
            {
                if(i > 1) printf(" ");
                printf("%d", ans[i]);
            }
            printf("\n");
        }
        else
        {
            for(int i = 1; i <= n; i++)
            {
                if(i > 1) printf(" ");
                printf("%d", a[n][k].num[i]);
            }
            printf("\n");
        }
    }
    return 0;
}