题目描述

在学习了许多关于太空探索的知识后，一个名叫 Ana 的小女孩想换个话题。

Ana 是一个非常喜欢回文串（即正着读和反着读都相同的字符串）的女孩。她已经学会了如何判断一个给定的字符串是否为回文串，但很快她对这个问题感到厌倦，于是她想出了一个更有趣的问题，现在需要你的帮助来解决：

给定一个只包含小写英文字母的字符串数组。你的任务是找出数组中有多少个“回文对”。一个“回文对”指的是一对字符串，满足以下条件：将这两个字符串拼接后，存在至少一种排列方式使得该字符串为回文串。换句话说，假设你有两个字符串，比如 "aab" 和 "abcac"，拼接后得到 "aababcac"，你需要判断是否存在该字符串的某种排列是回文串（在这个例子中，存在排列 "aabccbaa"）。

如果两个对中的字符串下标不同，则认为它们是不同的对。下标为 $(i,j)$ 的字符串对与 $(j,i)$ 被认为是相同的对。

输入格式

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

接下来的 $N$ 行，每行包含一个字符串（由小写英文字母 'a' 到 'z' 组成），表示输入数组的一个元素。

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

输出格式

输出一个整数，表示数组中有多少个回文对。

说明/提示

第一个样例：

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

由 ChatGPT 4.1 翻译

样例

3
aa
bb
cd

1

6
aab
abcac
dffe
ed
aa
aade

6