普及模拟赛 10 - E

时空限制

1000ms/1024MB

题目描述

一个长度为 $n$ 的序列被称为全排列，当且仅当其满足以下条件：

1. 序列中的每个元素均为 $[1,n]$ 中的整数。
2. 序列中的每个元素两两不同。

现在将长度为 $n$ 的 $n!$ 个全排列按如下方式进行从小到大排序：

1. 以序列中的逆序对个数为第一关键词。
2. 以序列的字典序为第二关键词。

请输出排名第 $k$​ 小的全排列。

输入格式

输入一行，共包含两个正整数 $n,k$。

输出格式

输出一行，包含 $n$ 个正整数。

样例输入1

4 10

样例输出1

1 4 3 2

样例输入2

5 120

样例输出2

5 4 3 2 1

样例输入3

16 12345678901234

样例输出3

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

样例输入4,5

见下发文件。

样例输出4,5

见下发文件。

数据范围

对于 $20\%$ 的数据，$1 \leq n \leq 8,1 \leq k \leq \min(n!,1000)$​。

对于 $40\%$ 的数据，$1 \leq n \leq 20,,1 \leq k \leq \min(n!,10^6)$。

对于 $60\%$ 的数据，$1 \leq n \leq 500,,1 \leq k \leq \min(n!,10^6)$。

对于 $80\%$ 的数据，$1 \leq n \leq 5000,,1 \leq k \leq \min(n!,4 \times 10^{18})$。

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5,1 \leq k \leq \min(n!,4\times 10^{18})$。