#D. [POI 2023/2024 R1] CzatBBB

    Type: RemoteJudge 1500ms 512MiB

[POI 2023/2024 R1] CzatBBB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 XXXI Olimpiada Informatyczna - I etap CzatBBB

题目描述

给出一个 nn 个字母的字符串 SS 和一个参数 kk,设 RR 为字符串 SS 的后 kk 个字母形成的字串。

假设字符串 SS'SS 添加一个新字母生成的新字符串。

添加的规则如下所示: 对于字母 XX 字母,计算它在字符串 SS 中紧接着 RR 出现的次数。出现频率最高的字母为新添加的字母,如果有多个出现频率最高的字母,取最小的一个。如果 RR 在字符串 SS 中的其他地方都没有出现,则取 X=aX = a。最后,我们扩展字符串 SS,在其末尾添加字母 XX

例如,设 S=abaaabababaS = \text{abaaabababa}k=3k = 3RR 与后一个字母一起出现的字串为的:abaa\text{abaa}abab\text{abab}abab\text{abab}。它最常与字母 b\text{b} 一起出现,因此我们在 SS 中加上 b\text{b},生成 S=abaaababababS' = \text{abaaabababab}

现在 S=abaaababababS' = \text{abaaabababab}R=babR = \text{bab}RR 与后一个字母一起出现的字串为:baba\text{baba}baba\text{baba},如 baba\text{baba}baba\text{baba},因此我们在 SS' 后面加上 aa

以此类推,这样的操作会进行无数次。

你的任务是编写一个程序,输出新字符串最后 aabb 个字符。

输入格式

第一行输入包含四个整数 nnkkaabb

第二行输入包含一个 nn 个字母的字符串,由小写英文字母组成的 nn 个字母字符串,表示单词 SS

输出格式

输出字符串 SS' 的第 aa 个字符 至第 bb 个字符,表示扩展单词 SS' 中位于以下位置的字母。

11 3 12 13
abaaabababa

ba

20 3 30 40
abcdabcdabcdabcdabcd

bcdabcdabcd

见附件
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

见附件
见附件

提示

对于所有的数据,2n1062\leq n\leq10^61k<n<a<b<10181\leq k<n<a<b<10^{18}b+1a106b+1-a\leq10^6,串只含小写字母。

子任务编号 附加限制 分值
1 n100n\leq100b1000b\leq1000 8
2 b108b\leq 10^8 10
3 n500n\leq 500,后缀 RR 的前一次出现将始终存在,并且每次出现后都会有相同的字母 16
4 后缀 RR 的前一次出现将始终存在,并且每次出现后都会有相同的字母 10
5 k20k\leq20b1010b\leq 10^{10},串只含 ab 16
6 无任何限制 40

周四下午训练

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2025-2-20 8:00
End at
2025-2-20 17:00
Duration
9 hour(s)
Host
Partic.
6