← 返回题目列表

Codeforces · 1045/I

I. 回文对

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

在了解了很多关于太空探索的知识后,一个名叫安娜的小女孩想要改变话题。

Ana 是一个喜欢回文(可以向后读和向前读一样的字符串)的女孩。她已经学会了如何检查给定的字符串是否是回文,但很快她就厌倦了这个问题,所以她想出了一个更有趣的问题,她需要你的帮助来解决它:

给你一个仅由小写字母组成的字符串数组。你的任务是找出数组中有多少个回文对。回文对是满足以下条件的一对字符串:两个字符串串联的至少一个排列是回文。换句话说,如果你有两个字符串,比如说“aab”和“abcac”,然后将它们连接成“aababcac”,我们必须检查这个新字符串是否存在一个回文排列(在本例中存在排列“aabccbaa”)。

如果字符串位于不同的索引上,则认为两对不同。索引为 $$$(i,j)$$$ 的字符串对被认为与 $$$(j,i)$$$ 相同。

输入

第一行包含一个正整数$$$N$$$ ($$$1 \le N \le 100\,000$$$),表示输入数组的长度。

接下来的 $$$N$$$ 行的每行都包含一个字符串(由从“a”到“z”的小写英文字母组成)——输入数组的一个元素。

输入数组中的字符总数将小于 $$$1\,000\,000$$$。

输出

输出一个数字,代表数组中有多少个回文对。

示例

输入 #1

3
aa
bb
cd

输出 #1

1

输入 #2

6
aab
abcac
dffe
ed
aa
aade

输出 #2

6

注意

第一个例子:

1. aa $$$+$$$ bb $$$\to$$$ abba。

第二个例子:

1. aab $$$+$$$ abcac $$$=$$$ aababcac $$$\to$$$ aabccbaa
2. aab $$$+$$$ aa $$$=$$$ aabaa
3. abcac $$$+$$$ aa $$$=$$$ abcacaa $$$\to$$$ aacbcaa
4. dffe $$$+$$$ ed $$$=$$$ dffeed $$$\to$$$ fdeedf
5. dffe $$$+$$$ aade $$$=$$$ dffeaade $$$\to$$$ adfaafde
6. ed $$$+$$$ aade $$$=$$$ edaade $$$\to$$$ aeddea