101372: [AtCoder]ABC137 C - Green Bin

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

Problem Statement

We will call a string obtained by arranging the characters contained in a string $a$ in some order, an anagram of $a$.

For example, greenbin is an anagram of beginner. As seen here, when the same character occurs multiple times, that character must be used that number of times.

Given are $N$ strings $s_1, s_2, \ldots, s_N$. Each of these strings has a length of $10$ and consists of lowercase English characters. Additionally, all of these strings are distinct. Find the number of pairs of integers $i, j$ $(1 \leq i < j \leq N)$ such that $s_i$ is an anagram of $s_j$.

Constraints

  • $2 \leq N \leq 10^5$
  • $s_i$ is a string of length $10$.
  • Each character in $s_i$ is a lowercase English letter.
  • $s_1, s_2, \ldots, s_N$ are all distinct.

Input

Input is given from Standard Input in the following format:

$N$
$s_1$
$s_2$
$:$
$s_N$

Output

Print the number of pairs of integers $i, j$ $(1 \leq i < j \leq N)$ such that $s_i$ is an anagram of $s_j$.


Sample Input 1

3
acornistnt
peanutbomb
constraint

Sample Output 1

1

$s_1 =$ acornistnt is an anagram of $s_3 =$ constraint. There are no other pairs $i, j$ such that $s_i$ is an anagram of $s_j$, so the answer is $1$.


Sample Input 2

2
oneplustwo
ninemodsix

Sample Output 2

0

If there is no pair $i, j$ such that $s_i$ is an anagram of $s_j$, print $0$.


Sample Input 3

5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa

Sample Output 3

4

Note that the answer may not fit into a $32$-bit integer type, though we cannot put such a case here.

Input

题意翻译

我们将调用通过以某种顺序排列字符串 $a$ 中包含的字符而获得的字符串,即 _anagram_。 例如,`greenbin` 是 `beginer` 的 _anagram_。 如此处所示,当同一字符多次出现时,该字符必须使用该次数。 给定 $N$ 个字符串 $s_1,s_2,\ldots,s_N$。每个字符串的长度为 $10$,由小写英文字符组成。 此外,所有这些字符串都是不同的。 找出整数对的数量 $(1 \leq i < j \leq N)$,使 $s_i$ 是 $s_j$ 的 _anagram_。

加入题单

上一题 下一题 算法标签: