分数: 700 点
问题陈述
Limak 可以重复删除字符串的前两个字符之一, 例如 abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx.
你被给予 N 不同的字符串 S_1, S_2, \ldots, S_N。 其中 N \cdot (N-1) / 2 对 (S_i, S_j), 利马克可以从多少对中获得一根绳子和另一根绳子?
约束
- 2 \leq N \leq 200\,000
- S_i 由小写英文字母组成
a-z. - S_i \neq S_j
- 1 \leq |S_i|
- |S_1| + |S_2| + \ldots + |S_N| \leq 10^6
输入
输入由标准输入按以下格式给出。
N S_1 S_2 \vdots S_N
输出
打印无序对的数量 (S_i, S_j) 其中 i \neq j 和 Limak 可以从另一个获取一个字符串。
示例输入 1
3 abcxyx cyx abc
示例输出 1
1
唯一好的一对是 (abcxyx, cyx).
示例输入 2
6 b a abc c d ab
示例输出 2
5
有五对好对: (b, abc), (a, abc), (abc, c), (b, ab), (a, ab).