← 返回题目列表

AtCoder · past17_i

I. 子序列对

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

问题陈述

你被给予 N 字符串 S_1,\ldots,S_N.

查找整数对的数量 (i,j) 这样:

  • 1 \leq i,j \leq N,和
  • S_i 是以下序列的子序列 S_j.
什么是子序列? 字符串的 A 子序列 是通过删除零个或多个位置的字符并连接剩余字符而不改变其顺序而获得的字符串。 例如, a, pe,和 apple 是子序列 apple,但是 ea 和 hoge 不是。

约束

  • 1 \leq N \leq 10^5
  • N 是一个整数。
  • S_i 是长度介于 1 和 5,包含在内,由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

N
S_1
\vdots
S_N

输出

打印答案。


示例输入 1

3
ps
past
post

示例输出 1

5

九对整数中 (i,j) 这样 1 \leq i,j \leq N,以下五个满足条件 S_i 是以下序列的子序列 S_j.

  • (i,j)=(1,1)
  • (i,j)=(1,2)
  • (i,j)=(1,3)
  • (i,j)=(2,2)
  • (i,j)=(3,3)

示例输入 2

5
a
aa
aaa
aaaa
aaaaa

示例输出 2

15

示例输入 3

2
hoge
hoge

示例输出 3

4