CF1450G Communism

请注意本题中非常规的内存限制。 在一个平行宇宙中，撒旦被称为“Trygub”。因此，他名字中的字母在古代就被从字母表中删除了。 政府有 $n$ 名工人站成一排，从左到右编号为 $1$ 到 $n$。他们的工作类别可以用一个长度为 $n$ 的字符串 $s$ 表示，其中字符 $s_i$ 表示第 $i$ 个工人的工作类别。 为了提升工人之间的平等，政府决定通过以下操作（可以执行任意多次，可能为零次）让所有人拥有相同的工作类别。 有一个固定的有理参数 $k=\frac{a}{b}$，用于描述说服公众的难易程度，并将在操作中使用。 每次操作时，政府首先选择当前至少有一名工人的某个工作类别 $x$。假设 $i_1,\ldots,i_m$（$i_1

第一行包含三个整数 $n, a, b$（$1 \le n \le 5000$，$1\le a\le b\le 10^5$）——工人数和参数 $k$ 的分子与分母。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成，表示每个工人的工作类别。字符串 $s$ 中不会出现 't'、'r'、'y'、'g'、'u'、'b' 这几个字母。

输出一个整数 $c$，表示可达的工作类别数量，随后输出 $c$ 个按字典序排列的可达工作类别字符，用空格分隔。

第一次操作必须选择工作类别 'i'，因为其他所有类别都无法满足条件，因此 'i' 不是可达的。 下面展示了如何获得 'c'、'm' 和 'o'。方括号表示包含所有被选中类别工人的区间，红色表示该类别，蓝色表示更改后的新类别。 3. 获得 'c'： 1. （$\texttt{com}\color{red}{\texttt{[i]}}\texttt{com} \rightarrow \texttt{com}\color{#1E90FF}{\texttt{[o]}}\texttt{com}$） 2. （$\texttt{c}\color{red}{\texttt{[o}}\texttt{m}\color{red}{\texttt{o}}\texttt{c}\color{red}{\texttt{o]}}\texttt{m} \rightarrow \texttt{c}\color{#1E90FF}{\texttt{[m}}\texttt{m}\color{#1E90FF}{\texttt{m}}\texttt{c}\color{#1E90FF}{\texttt{m]}}\texttt{m}$） 3. （$\texttt{c}\color{red}{\texttt{[mmm}}\texttt{c}\color{red}{\texttt{mm]}} \rightarrow \texttt{c}\color{#1E90FF}{\texttt{[ccc}}\texttt{c}\color{#1E90FF}{\texttt{cc]}}$） 4. 获得 'm'： 1. （$\texttt{com}\color{red}{\texttt{[i]}}\texttt{com} \rightarrow \texttt{com}\color{#1E90FF}{\texttt{[o]}}\texttt{com}$） 2. （$\texttt{c}\color{red}{\texttt{[o}}\texttt{m}\color{red}{\texttt{o}}\texttt{c}\color{red}{\texttt{o]}}\texttt{m} \rightarrow \texttt{c}\color{#1E90FF}{\texttt{[c}}\texttt{m}\color{#1E90FF}{\texttt{c}}\texttt{c}\color{#1E90FF}{\texttt{c]}}\texttt{m}$） 3. （$\color{red}{\texttt{[cc}}\texttt{m}\color{red}{\texttt{ccc]}}\texttt{m} \rightarrow \color{#1E90FF}{\texttt{[mm}}\texttt{m}\color{#1E90FF}{\texttt{mmm]}}\texttt{m}$） 5. 获得 'o'： 1. （$\texttt{com}\color{red}{\texttt{[i]}}\texttt{com} \rightarrow \texttt{com}\color{#1E90FF}{\texttt{[c]}}\texttt{com}$） 2. （$\color{red}{\texttt{[c}}\texttt{om}\color{red}{\texttt{cc]}}\texttt{om} \rightarrow \color{#1E90FF}{\texttt{[m}}\texttt{om}\color{#1E90FF}{\texttt{mm]}}\texttt{om}$） 3. （$\color{red}{\texttt{[m}}\texttt{o}\color{red}{\texttt{mmm}}\texttt{o}\color{red}{\texttt{m]}} \rightarrow \color{#1E90FF}{\texttt{[o}}\texttt{o}\color{#1E90FF}{\texttt{ooo}}\texttt{o}\color{#1E90FF}{\texttt{o]}}$） 由 ChatGPT 4.1 翻译