← 返回题目列表

Codeforces · 744/E

E. 红牛掌握循环移位

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

红牛的老师听说红牛学会了循环移位,决定给他出下面的题。

给定一个包含列表 A 中包含的 n 个字符串 s1, s2, ..., sn 的列表。

如果满足以下条件,则字符串列表 X 被称为稳定的。

首先,消息被定义为列表 X 的某些元素的串联。您可以根据需要多次使用任意元素,并且可以以任意顺序串联这些元素。让 SX 表示您可以从列表中构造的所有消息的集合。当然,如果您的列表非空,则该集合具有无限大小。

如果满足以下条件,则称单个消息良好:

- 假设消息是 k 个字符串 w1, w2, ..., wk 的串联,其中每个 wi 是 X 的一个元素。
- 考虑 |w1| + |w2| + ... + |周|字符串的循环移位。令 m 为作为 SX 元素的字符串的这些循环移位的数量。
- 当且仅当 m 完全等于 k ​​时,消息才是好的。

列表 X 被称为稳定当且仅当 SX 的每个元素都是好的。

如果 L 是稳定列表,则令 f(L) 为 1,否则为 0。

求 f(L) 的和,其中 L 是 A 的非空连续子列表(总共有 $$\frac{n(n+1)}{2}$$ 连续子列表)。

输入

输入的第一行将包含一个整数 n (1 ≤ n ≤ 30),表示列表中字符串的数量。

接下来的 n 行将分别包含一个字符串 si ($$1 \leq | s _ { i } |, \sum _ { i = 1 } ^ { n } | s _ { i } | \leq 100 \, 000$$)。

输出

打印单个整数,即稳定的非空连续子列表的数量。

示例

输入 #1

4
a
ab
b
bba

输出 #1

7

输入 #2

5
hh
ee
ll
ll
oo

输出 #2

0

输入 #3

6
aab
ab
bba
b
ab
c

输出 #3

13

注意

对于第一个示例,需要考虑 10 个子列表。子列表 ["a", "ab", "b"]、["ab", "b", "bba"] 和 ["a", "ab", "b", "bba"] 不稳定。其他七个子列表稳定。

例如,X = ["a", "ab", "b"] 是不稳定的,因为消息 "ab" + "ab" = "abab" 有四个循环移位 ["abab", "baba", "abab", "baba"],它们都是 SX 的元素。