4070 - 书名整理

题目描述

图书馆最近收到了 N 本新书,这批书比较独特,独特之处在于每本书的书名都是由 10 个英文小写字母组成,且 N 本新书的书名互不相同

为了方便管理,图书馆决定请图书管理员小 A 将这些书名进行整理。整理过程中,小 A 发现,虽然这些书名互不相同,但某些书可以通过调整书名中 10 个小写字母的前后顺序,得到另外一些书的书名。

例如,书名 libraryman 和 书名 manlibrary 就可以通过调整其中一本书的书名中的字母的前后顺序,得到另外一本书的书名。形式化的讲,这两本书包含的字母完全相同,只是顺序不同。

A 想要调查一下,有多少对书的书名,符合上述规律。即:如果 N 本书的书名为 S_1, S_2, \ldots, S_N,其中第 i 本书和第 j 本书的书名符合上述要求,且 i \lt j,则这对书将计入统计的答案。

输入

输入的第一行包含一个整数 N,表示图书的数量。

接下来的 N 行,每行包含一个长度为 10 的字符串 S_i,表示第 i 本书的书名。所有书名均由小写英文字母组成,且互不相同。

输出

输出一个整数,表示所有匹配的编号对的总数。

样例

输入

5
listenwind
windlisten
adormitory
adirtyroom
dormitorya

输出

4

输入

6
ababababab
aaaaabbbbb
bbbbbaaaaa
aabbaabbab
abcdefghij
ijabcdefgh

输出

7

输入

10
abcdefghij
bcdefghija
cdefghijab
defghijabc
efghijabcd
fghijabcde
ghijabcdef
aabbccddee
abcdeabcde
thisisbook

输出

22
说明

样例 1 说明

共有 5 本书,其中:第 1 2 本、第 3 4 本、第 3 5 本、第 4 5 本,均符合题意,因此共有 4 对。

请注意:第 1 2 本书,形成的书名对,只能被统计一次。

数据范围

对于 50\% 的数据,满足 1 \leq N \leq 1000

对于 100\% 的数据,满足 2 \leq N \leq 10^5,第 i 本书的书名 S_i 的长度为 10,且由小写英文字母组成,所有书名互不相同。

测试点编号N特殊性质
1N=2A
2N=2
3N=3
4N=5
5N=1000
6 \sim 10N \leq 10^5

特殊性质 A:对于测试点 1 读入的 2 个字符串,数据保证,两个字符串中的字符,均按照 ascii 码从小到大的顺序排序。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 入门


上一题 下一题