Dasha and Nightmares
Contest: Codeforces Round 855 (Div. 3)
Difficulty rating: 1900
Tags: bitmasks, hashing, meet-in-the-middle, strings

Dasha, an excellent student, is studying at the best mathematical lyceum in the country. Recently, a mysterious stranger brought $$$n$$$ words consisting of small latin letters $$$s_1, s_2, \ldots, s_n$$$ to the lyceum. Since that day, Dasha has been tormented by nightmares.

Consider some pair of integers $$$\langle i, j \rangle$$$ ($$$1 \le i \le j \le n$$$). A nightmare is a string for which it is true:

- It is obtained by concatenation $$$s_{i}s_{j}$$$;
- Its length is odd;
- The number of different letters in it is exactly $$$25$$$;
- The number of occurrences of each letter that is in the word is odd.

For example, if $$$s_i=$$$ "abcdefg" and $$$s_j=$$$ "ijklmnopqrstuvwxyz", the pair $$$\langle i, j \rangle$$$ creates a nightmare.

Dasha will stop having nightmares if she counts their number. There are too many nightmares, so Dasha needs your help. Count the number of different nightmares.

Nightmares are called different if the corresponding pairs $$$\langle i, j \rangle$$$ are different. The pairs $$$\langle i_1, j_1 \rangle$$$ and $$$\langle i_2, j_2 \rangle$$$ are called different if $$$i_1 \neq i_2$$$ or $$$j_1 \neq j_2$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of words.

The following $$$n$$$ lines contain the words $$$s_1, s_2, \ldots, s_n$$$, consisting of small latin letters.

It is guaranteed that the total length of words does not exceed $$$5 \cdot 10^6$$$.

Output format:
Print a single integer — the number of different nightmares.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test, nightmares are created by pairs $$$\langle 1, 3 \rangle$$$, $$$\langle 2, 5 \rangle$$$, $$$\langle 3, 4 \rangle$$$, $$$\langle 6, 7 \rangle$$$, $$$\langle 9, 10 \rangle$$$.

Example input:
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz

Example output:
5

Editorial:
Observation $$$1$$$: the product of odd numbers is odd, so the condition for the length of nightmare is automatically completed.
Denote by $$$f(x)$$$ the number of ones in binary representation of $$$x$$$. Let's enumerate the letters of the Latin alphabet from $$$0$$$ to $$$25$$$.
Observation $$$2$$$: for each word, it is enough to know the set of letters included in it and the evenness of their numbers. There are only $$$26$$$ letters in the alphabet, so it is convenient to store the word characteristic $$$s_i$$$ as a pair of masks $$$\langle a_i, b_i \rangle$$$. The bit with the number $$$j$$$ in $$$a_i$$$ will be responsible for the availability of the letter $$$j$$$ in $$$s_i$$$. The bit with the number $$$j$$$ in $$$b_i$$$ will be responsible for the evenness of the number of letters $$$j$$$ in $$$s_i$$$.
Observation $$$3$$$: strings $$$s_is_j$$$ creates nightmare if and only if $$$f(a_i|a_j) = f(b_i \oplus b_j) = 25$$$.
Let's fix the number $$$k$$$ — the index of the letter that will not be in nightmares. Let's throw out all the words with the letter $$$k$$$, now we can look at the words in turn and look for a pair of them among those already considered. It is easy to see that the condition $$$f(a_i| a_j) = 25$$$ follows from the condition $$$f(b_i\oplus b_j) = 25$$$ if one letter is banned.
To count the number of pairs that include our word, we need to count the number of words with the characteristic $$$b_j = b_i \oplus (2^{26}-1)$$$. We can do this by bin-searching through a sorted array of $$$b$$$ or using standard data structures. We got the solution for $$$O(\sum |s| + 26 \cdot n \cdot \log n)$$$.