← 返回题目列表

Codeforces · 1800/F

F. 达莎和噩梦

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

达莎,一名优秀的学生,正在全国最好的数学学院学习。最近,一位神秘的陌生人将$$$n$$$由小拉丁字母$$$s_1、s_2、\ldots、s_n$$$组成的单词带到了学园。从那天起,达莎就一直被噩梦所折磨。

考虑一些整数对 $$$\langle i, j \rangle$$$ ($$$1 \le i \le j \le n$$$)。噩梦是一个真实的字符串:

- 通过$$$s_{i}s_{j}$$$串联得到;
- 其长度为奇数;
- 其中不同字母的数量正好是$$$25$$$;
- 单词中每个字母出现的次数是奇数。

例如,如果 $$$s_i=$$$ "abcdefg" 和 $$$s_j=$$$ "ijklmnopqrstuvwxyz",则 $$$\langle i, j \rangle$$$ 配对会造成一场噩梦。

如果达莎数清他们的数量,她就会停止做噩梦。噩梦太多了,达莎需要你的帮助。数一下不同噩梦的数量。

如果对应的 $$$\langle i, j \rangle$$$ 不同,则噩梦被称为不同。如果 $$$i_1 \neq i_2$$$ 或 $$$j_1 \neq j_2$$$ 则 $$$\langle i_1, j_1 \rangle$$$ 和 $$$\langle i_2, j_2 \rangle$$$ 对被称为不同。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 单词数。

以下 $$$n$$$ 行包含单词 $$$s_1, s_2, \ldots, s_n$$$,由小拉丁字母组成。

保证单词总长度不超过$$$5 \cdot 10^6$$$。

输出

打印一个整数——不同噩梦的数量。

示例

输入 #1

10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz

输出 #1

5

注意

在第一个测试中,噩梦是由 $$$\langle 1, 3 \rangle$$$, $$$\langle 2, 5 \rangle$$$, $$$\langle 3, 4 \rangle$$$, $$$\langle 6, 7 \rangle$$$, $$$\langle 9, 10 \rangle$$$ 创建的。