← 返回题目列表

Codeforces · 766/C

C. 马哈茂德和一条消息

中文机器翻译题面 查看原题

Mahmoud 写了一条长度为 n 的消息 s。他想把它作为生日礼物送给喜欢弦乐的朋友莫阿兹。他把它写在一张神奇的纸上,但他很惊讶,因为在写字符串时有些字符消失了。那是因为这张神奇的纸不允许将英文字母中的第i个字符以长度超过ai的字符串写在上面。例如,如果a1 = 2,他就不能在这张纸上以长度为3或更长的字符串写出字符“a”。允许使用字符串“aa”,而不允许使用字符串“aaa”。

Mahmoud 决定将消息分割成一些非空子串,以便他可以将每个子串写在独立的魔法纸上并满足条件。它们的长度之和应该是n并且它们不应该重叠。例如,如果a1 = 2,他想发送字符串“aaa”,他可以将其拆分为“a”和“aa”并使用2张魔纸,或者分为“a”,“a”和“a”并使用3张魔纸。他无法将其拆分为“aa”和“aa”,因为它们的长度之和大于n。如果满足条件,他可以将消息拆分为单个字符串。

字符串 s 的子字符串是由字符串 s 中的一些连续字符组成的字符串,字符串“ab”、“abc”和“b”是字符串“abc”的子字符串,而字符串“acb”和“ac”则不是。任何字符串都是其自身的子字符串。

当 Mahmoud 思考如何分割消息时,Ehab 告诉他分割消息的方法有很多种。之后,马哈茂德问了你三个问题:

- 有多少种方法可以将字符串分割成子字符串,使得每个子字符串都满足魔纸的条件,它们的长度之和为n并且它们不重叠?以 109 + 7 为模计算答案。
- 某些有效分割中可以出现的子字符串的最大长度是多少?
- 消息中至少可以包含多少个子字符串?

如果分割位置组不同,则两种方式被认为是不同的。例如,拆分“aa|a”和“a|aa”被视为消息“aaa”的不同拆分。

输入

第一行包含一个整数 n (1 ≤ n ≤ 103),表示消息的长度。

第二行包含长度为n的消息s,由小写英文字母组成。

第三行包含 26 个整数 a1, a2, ..., a26 (1 ≤ ax ≤ 103) – 每个字母可以出现的子字符串的最大长度。

输出

打印三行。

在第一行中打印将消息拆分为子字符串并满足问题中提到的条件模 109 + 7 的方法数。

在第二行中打印所有路径中最长子字符串的长度。

在第三行中打印所有方式的最小子字符串数。

示例

输入 #1

3
aab
2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出 #1

3
2
2

输入 #2

10
abcdeabcde
5 5 5 5 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出 #2

401
4
3

注意

在第一个示例中,分割消息的三种方法是:

- a|a|b
- aa|b
- a|ab

最长的子串是长度为 2 的“aa”和“ab”。

“a|ab”或“aa|b”中子字符串的最小数量为 2。

请注意,“aab”不是可能的拆分,因为字母“a”出现在长度为 3 的子字符串中,而 a1 = 2。