[POI 2023/2024 R1] CzatBBB

Luogu

IDLGP9922

Time1500ms

Memory512MB

DifficultyP6

POI（波兰）2023

给出一个 $n$ 个字母的字符串 $S$ 和一个参数 $k$，设 $R$ 为字符串 $S$ 的后 $k$ 个字母形成的字串。假设字符串 $S'$ 为 $S$ 添加一个新字母生成的新字符串。添加的规则如下所示：对于字母 $X$ 字母，计算它在字符串 $S$ 中紧接着 $R$ 出现的次数。出现频率最高的字母为新添加的字母，如果有多个出现频率最高的字母，取最小的一个。如果 $R$ 在字符串 $S$ 中的其他地方都没有出现，则取 $X = a$。最后，我们扩展字符串 $S$，在其末尾添加字母 $X$。例如，设 $S = \text{abaaabababa}$，$k = 3$ 则 $R$ 与后一个字母一起出现的字串为的：$\text{abaa}$、$\text{abab}$、$\text{abab}$。它最常与字母 $\text{b}$ 一起出现，因此我们在 $S$ 中加上 $\text{b}$，生成 $S' = \text{abaaabababab}$。现在 $S' = \text{abaaabababab}$，$R = \text{bab}$，$R$ 与后一个字母一起出现的字串为：$\text{baba}$、$\text{baba}$，如 $\text{baba}$、$\text{baba}$，因此我们在 $S'$ 后面加上 $a$。以此类推，这样的操作会进行无数次。你的任务是编写一个程序，输出新字符串最后 $a$ 至 $b$ 个字符。 ## Input 第一行输入包含四个整数 $n$、$k$、$a$ 和 $b$。第二行输入包含一个 $n$ 个字母的字符串，由小写英文字母组成的 $n$ 个字母字符串，表示单词 $S$。 ## Output 输出字符串 $S'$ 的第 $a$ 个字符至第 $b$ 个字符，表示扩展单词 $S'$ 中位于以下位置的字母。 [samples] ## Background 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [CzatBBB](https://sio2.mimuw.edu.pl/c/oi31-1/p/cza/)。 ## Note 对于所有的数据，$2\leq n\leq10^6$，$1\leq k<n<a<b<10^{18}$，$b+1-a\leq10^6$，串只含小写字母。 | 子任务编号 | 附加限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $n\leq100$，$b\leq1000$ | 8 | | 2 | $b\leq 10^8$ | 10 | | 3 | $n\leq 500$，后缀 $R$ 的前一次出现将始终存在，并且每次出现后都会有相同的字母 | 16 | | 4 | 后缀 $R$ 的前一次出现将始终存在，并且每次出现后都会有相同的字母 | 10 | | 5 | $k\leq20$，$b\leq 10^{10}$，串只含 `ab` | 16 | | 6 | 无任何限制 | 40 |

Samples

Input #1

11 3 12 13
abaaabababa

Output #1

ba

Input #2

20 3 30 40
abcdabcdabcdabcdabcd

Output #2

bcdabcdabcd

Input #3

见附件

Output #3

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Input #4

见附件

Output #4

见附件

API Response (JSON)

{
  "problem": {
    "name": "[POI 2023/2024 R1] CzatBBB",
    "description": {
      "content": "给出一个 $n$ 个字母的字符串 $S$ 和一个参数 $k$，设 $R$ 为字符串 $S$ 的后 $k$ 个字母形成的字串。 假设字符串 $S'$ 为 $S$ 添加一个新字母生成的新字符串。 添加的规则如下所示： 对于字母 $X$ 字母，计算它在字符串 $S$ 中紧接着 $R$ 出现的次数。出现频率最高的字母为新添加的字母，如果有多个出现频率最高的字母，取最小的一个。如果 $R$ 在字符串 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9922"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个 $n$ 个字母的字符串 $S$ 和一个参数 $k$，设 $R$ 为字符串 $S$ 的后 $k$ 个字母形成的字串。\n\n假设字符串 $S'$ 为 $S$ 添加一个新字母生成的新字符串。\n\n添加的规则如下所示： 对于字母 $X$ 字母，计算它在字符串 $S$ 中紧接着 $R$ 出现的次数。出现频率最高的字母为新添加的字母，如果有多个出现频率最高的字母，取最小的一个。如果 $R$ 在字符串 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments