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 翻译