1045I.md (2232B)
1 Source: https://codeforces.com/problemset/problem/1045/I 2 3 I. Palindrome Pairs 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 After learning a lot about space exploration, a little girl named Ana wants to change the subject. 22 23 Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it's a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it: 24 25 You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let's say "aab" and "abcac", and you concatenate them into "aababcac", we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation "aabccbaa"). 26 27 Two pairs are considered different if the strings are located on different indices. The pair of strings with indices $(i,j)$ is considered the same as the pair $(j,i)$. 28 29 Input 30 31 The first line contains a positive integer $N$ ($1 \le N \le 100\,000$), representing the length of the input array. 32 33 Eacg of the next $N$ lines contains a string (consisting of lowercase English letters from 'a' to 'z') — an element of the input array. 34 35 The total number of characters in the input array will be less than $1\,000\,000$. 36 37 Output 38 39 Output one number, representing how many palindrome pairs there are in the array. 40 41 Examples 42 43 Input 44 45 ``` 46 3 47 aa 48 bb 49 cd 50 ``` 51 52 Output 53 54 ``` 55 1 56 ``` 57 58 Input 59 60 ``` 61 6 62 aab 63 abcac 64 dffe 65 ed 66 aa 67 aade 68 ``` 69 70 Output 71 72 ``` 73 6 74 ``` 75 76 Note 77 78 The first example: 79 80 1. aa $+$ bb $\to$ abba. 81 82 The second example: 83 84 1. aab $+$ abcac $=$ aababcac $\to$ aabccbaa 85 2. aab $+$ aa $=$ aabaa 86 3. abcac $+$ aa $=$ abcacaa $\to$ aacbcaa 87 4. dffe $+$ ed $=$ dffeed $\to$ fdeedf 88 5. dffe $+$ aade $=$ dffeaade $\to$ adfaafde 89 6. ed $+$ aade $=$ edaade $\to$ aeddea