C - N!÷K番目の単語 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋語には 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 行目には高橋語の単語の中で辞書順で小さい方から 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