CF1045I Palindrome Pairs

在学习了许多关于太空探索的知识后，一个名叫 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 翻译