← 返回题目列表

Codeforces · 1902/E

E. 折叠琴弦

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

给你 $$$n$$$ 字符串 $$$s_1, s_2, \dots, s_n$$$,由小写拉丁字母组成。令 $$$|x|$$$ 为字符串 $$$x$$$ 的长度。

设两个字符串 $$$a$$$ 和 $$$b$$$ 的折叠 $$$C(a, b)$$$ 为以下操作:

- 如果 $$$a$$$ 为空,$$$C(a, b) = b$$$;
- 如果 $$$b$$$ 为空,则 $$$C(a, b) = a$$$;
- 如果 $$$a$$$ 的最后一个字母等于 $$$b$$$ 的第一个字母,则 $$$C(a, b) = C(a_{1,|a|-1}, b_{2,|b|})$$$,其中 $$$s_{l,r}$$$ 是 $$$s$$$ 从第 $$$l$$$ 到第一个字母的子串第 $$$r$$$ 个;
- 否则,$$$C(a, b) = a + b$$$, i. e.两个字符串的串联。

计算 $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。

接下来的 $$$n$$$ 行包含一个字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 10^6$$$),由小写拉丁字母组成。

字符串的总长度不超过$$$10^6$$$。

输出

打印单个整数 — $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$。

示例

输入 #1

3
aba
ab
ba

输出 #1

20

输入 #2

5
abab
babx
xab
xba
bab

输出 #2

126