← 返回题目列表

Codeforces · 1129/C

C. 摩尔斯电码

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

在摩尔斯电码中,英文字母表中的字母表示为从 $$$1$$$ 到 $$$4$$$ 的某个长度的字符串。此外,英语字母的每个摩尔斯电码表示仅包含点和破折号。在此任务中,我们将用“0”表示点,用“1”表示破折号。

因为存在 $$$2^1+2^2+2^3+2^4 = 30$$$ 个长度为 $$$1$$$ 到 $$$4$$$ 且仅包含“0”和/或“1”的字符串,所以并非所有这些字符串都对应于 $$$26$$$ 英文字母之一。特别地,每个长度至多$$$4$$$的“0”和/或“1”字符串翻译成不同的英文字母,除了以下四个不对应于任何英文字母的字符串:“0011”、“0101”、“1110”和“1111”。

您将使用字符串 $$$S$$$,该字符串最初为空。对于 $$$m$$$ 次,将在 $$$S$$$ 上附加一个点或破折号,一次一个。您的任务是在对字符串 $$$S$$$ 进行每次修改后,查找并报告用摩尔斯电码 $$$S$$$ 的某些子字符串表示的非空英文字母序列的数量。

由于答案可能非常巨大,请以 $$$10^9 + 7$$$ 为模打印它们。

输入

第一行包含一个整数 $$$m$$$ ($$$1 \leq m \leq 3\,000$$$) — 对 $$$S$$$ 的修改次数。

接下来的 $$$m$$$ 行包含“0”(代表点)或“1”(代表破折号),指定应将哪个字符附加到 $$$S$$$。

输出

打印$$$m$$$行,其中第$$$i$$$行是对$$$S$$$进行第$$$i$$$修改后的答案。

示例

输入 #1

3
1
1
1

输出 #1

1
3
7

输入 #2

5
1
0
1
0
1

输出 #2

1
4
10
22
43

输入 #3

9
1
1
0
0
0
1
1
0
1

输出 #3

1
3
10
24
51
109
213
421
833

注意

让我们考虑将所有字符附加到 $$$S$$$ 后的第一个样本,因此 S 是“111”。

如您所见,“1”、“11”和“111”都对应于某个不同的英文字母。事实上,它们分别被翻译成“T”、“M”和“O”。因此,用摩尔斯电码 $$$S$$$ 的某个子串表示的所有非空英文字母序列如下。

1.“T”(翻译为“1”)
2.“M”(翻译为“11”)
3.“O”(翻译为“111”)
4.“TT”(翻译为“11”)
5.“TM”(翻译为“111”)
6.“MT”(翻译为“111”)
7.“TTT”(翻译为“111”)

虽然此任务不需要,但可以在此处找到从英语字母到摩尔斯电码的转换表。