← 返回题目列表

AtCoder · arc047_c

C. N!÷第 K 个字

中文机器翻译题面 查看原题

問題文

高桥语言有 有 N 类型的字符。

为了方便起见,在这个问题中,我们将按字典顺序升序书写每个字母。 我们将分配并处理 1 ~ N 整数。

所有高桥的话 N 由字符组成,N 类型的所有字符都完全相同 包含 1 块。 而且,所有这些字符串都是高桥词。

换句话说,高桥的话是 有 N! 件。

是 小于或等于 N 的正整数 给出了 K ,所以在高桥单词中,按照字典顺序从最小的开始 找到第 N! ÷ K 个单词。


入力

输入将以以下形式通过标准输入给出。

N K
  • 1 在线 2 整数 编写一个程序来查找 N, K(1 ≦ K ≦ N ≦ 10^5) 用空格分隔。 如果正确答案是满足

部分点

针对此问题设置了部分分数。

  • 1 ≦ N ≦ 20 的数据集 如果正确答案是满足 30 分被给予。
  • 1 ≦ N ≦ 10^5 的数据集,则进一步 给出 70 点。总共100点。

出力

输出是 由 N 行组成。 i 在第一行中,Takahashi 中的单词按照字典顺序从最小的单词开始列出。 N! ÷ K 这个词 i 打印与字符号对应的整数。 在输出末尾插入换行符。 按字典顺序从小到大对


入力例1

4 3

出力例1

2
1
4
3

1,2,3,4 进行排序 必须输出第 4! ÷ 3 = 8 个字符。 高桥单词按字典顺序从最小到最小 枚举 8 时

1, 2, 3, 4

1, 2, 4, 3

1, 3, 2, 4

1, 3, 4, 2

1, 4, 2, 3

1, 4, 3, 2

2, 1, 3, 4

2, 1, 4, 3

。因此 2, 1, 4, 3是您应该查找的词。


入力例2

11 7

出力例2

2
7
9
5
4
11
10
8
6
3
1