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

高桥语有 $N$ 种不同的字母。 在本题中，为了方便起见，我们将这些字母按字典序从小到大分别编号为 $1$ 到 $N$ 的整数。 高桥语的单词全部由 $N$ 个字母组成，并且每种字母恰好出现一次。也就是说，每个这样的字符串都是高桥语的单词。 因此，高桥语的单词共有 $N!$ 个。 现在给定一个不超过 $N$ 的正整数 $K$，请你求出高桥语的单词中，按字典序从小到大排列后第 $N! \div K$ 个单词。

输入从标准输入读入，格式如下： > $N$ $K$ - 第 $1$ 行包含两个用空格分隔的整数 $N,\ K$，满足 $1 \leq K \leq N \leq 10^5$。

输出共 $N$ 行。第 $i$ 行输出高桥语的单词中，按字典序从小到大排列后第 $N! \div K$ 个单词的第 $i$ 个字母所对应的整数。输出末尾需要换行。

## 部分分 本题设有部分分。 - 若你能正确解决 $1 \leq N \leq 20$ 的数据集，将获得 $30$ 分。 - 若你能正确解决 $1 \leq N \leq 10^5$ 的数据集，将再获得 $70$ 分，总分为 $100$ 分。 ## 样例解释 1 对于 $1,2,3,4$ 的全排列，按字典序从小到大排列后第 $4! \div 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$ 就是所求的单词。 由 ChatGPT 4.1 翻译