Узнав много нового об освоении космоса, маленькая девочка по имени Ана хочет сменить тему исследования.
Ана это девушка, которая любит палиндромы (строки, которые читаются одинаково слева-направо и справа-налево). Она научилась проверять данную строку на палиндромность, но вскоре ей надоела эта задача, она придумала более интересную и теперь ей нужна ваша помощь, чтобы ее решить:
Дан массив строк, состоящих из строчных букв латинского алфавита. Ваша задача — найти сколько палиндромных пар в массиве. Палиндромная пара — это пара строк, такая, что выполняется следующее условие: по крайней мере одна перестановка букв в конкатенации двух строк является палиндромом. Другими словами, если у вас есть две строки, скажем, «aab» и «abcac», мы объединяем их в «aababcac», и должны проверить, существует ли такая перестановка букв этой новой строки, что получится палиндром (в этом случае можно переставить буквы так, чтобы получить «aabccbaa»).
Две пары строк считаются разными, если строки находятся на разных позициях. Пара строк $$$(i,j)$$$ считается совпадающей с парой $$$(j,i)$$$.
В первой строке входного файла записано целое число $$$N$$$ ($$$1 \le N \le 100\,000$$$), обозначающее длину данного массива.
Следующие $$$N$$$ строк содержат по одной строке (состоящей только из латинских строчных букв от «a» до «z») — элементу исходного массива.
Суммарное количество символов во всех строках в массиве не превосходит $$$1\,000\,000$$$.
Выведите одно целое число, описывающее сколько палиндромных пар есть в этом массиве.
3
aa
bb
cd
1
6
aab
abcac
dffe
ed
aa
aade
6
Первый пример:
Второй пример:
Название |
---|