AT_arc047_c [ARC047C] N!÷K番目の単語

[problemUrl]: https://atcoder.jp/contests/arc047/tasks/arc047_c 高橋語には $ N $ 種類の文字があります。 この問題では便宜上、各文字に辞書順で小さい順に $ 1 $ ～ $ N $ の整数を割り振って扱うことにします。 高橋語の単語は全て $ N $ 文字からなり、$ N $ 種類の文字が全てちょうど $ 1 $ 個ずつ含まれます。 また、そのような文字列は全て高橋語の単語です。 つまり、高橋語の単語は $ N! $ 個あります。 ある $ N $ 以下の正の整数 $ K $ が与えられるので、高橋語の単語の中で辞書順で小さい方から $ N!\ ÷\ K $ 番目の単語を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ - $ 1 $ 行目には $ 2 $ つの整数 $ N,\ K(1\ ≦\ K\ ≦\ N\ ≦\ 10^5) $ が空白区切りで与えられます。

出力は $ N $ 行からなる。 $ i $ 行目には高橋語の単語の中で辞書順で小さい方から $ N!\ ÷\ K $ 番目の単語の $ i $ 文字目の文字に対応する整数を出力せよ。 出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ N\ ≦\ 20 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 - $ 1\ ≦\ N\ ≦\ 10^5 $ を満たすデータセットに正解した場合はさらに $ 70 $ 点が与えられる。合計で$ 100 $点となる。 ### Sample Explanation 1 $ 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 $が求めるべき単語です。