P14547 [IO 2024 #3] 莫图努伊部落的语言

对我们来说，屏幕上当然显示的是说我们母语的角色，但莫图努伊部落的母语要复杂得多。 该语言总共有 $n$ 个字母，每个字母对应的声音我们用数字 $a_1, \ldots, a_n$ 表示。不同的字母可能对应相同的声音。该语言中恰好有 $2^n - 1$ 个单词，每个单词都是这 $n$ 个字母的任意子序列（单词中字母的顺序与字母表中的顺序一致）。 用 $s_i$ 表示按字典序排列的第 $i$ 个单词的 **发音**。即取该语言的所有单词，写出每个单词的声音序列，并按升序排列这些序列。这里我们认为单词 $x$ 小于单词 $y$，如果要么 $x$ 的声音序列是 $y$ 声音序列的前缀，要么 $x$ 中第一个不同的声音小于 $y$ 中对应的声音。 你的任务是找到莫图努伊岛部落语言中发音最小的 $k$ 个单词。由于这些单词的总长度可能过大，请改为输出这些单词的哈希值，其中单词 $s = \overline{c_1 c_2 \ldots c_k}$ 的哈希值为 $$h(s) = (a_{c_1} B^{k-1} + a_{c_2} B^{k-2} + \ldots + a_{c_{k-1}} B + a_{c_k}) \bmod M$$ 其中 $B$ 和 $M$ 是预先给定的参数。

第一行输入包含整数 $n$、$k$、$B$ 和 $M$——分别表示字母表中的字母数量、你感兴趣的单词数量和哈希参数（$1 \le k, n \le 10^5$；$ k \le 2^n - 1$；$1 \le B, M \le 10^6$）。 第二行列出 $n$ 个整数 $a_i$——每个字母的声音编号（$1 \le a_i \le 10^5$）。

对于按字典序排列最小的 $k$ 个语言单词，依次输出它们发音的哈希值，每行一个。

在第一个样例中，单词的顺序为：$\overline{1}$、$\overline{1,2}$、$\overline{2}$。 在第二个样例中，单词的发音为：$\overline{1}$、$\overline{1}$、$\overline{1,3}$、$\overline{1,3,1}$、$\overline{3}$、$\overline{3,1}$。 --- 翻译由 DeepSeek V3 完成