Description:


A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, "dad", "eye" and "racecar" are all palindromes, but "odd", "see" and "orange" are not palindromes.

Given n strings, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes.

Input:


The first line of input file contains the number of strings n. The following n lines describe each string:

The i+1-th line contains the length of the i-th string li, then a single space and a string of li small letters of English alphabet.

You can assume that the total length of all strings will not exceed 2,000,000. Two strings in different line may be the same.

Output:


Print out only one integer, the number of palindromes.

Sample Input:


Sample Output:


题解:


题目大意:给出n个字符串(总长不超过2000000),求出所有满足将 \(s_i\)\(s_j\)\(i, j\in [1, n]\) 拼接到一起是回文串的 \((i, j)\) 的对数。

我们发现 \(s_i\) 拼上 \(s_j\) 是回文串当且仅当 \(s_j\) 的反串和 \(s_i\) 的LCP长度为 \(min(len(s_i), len(s_j))\) ,且去掉匹配的部分剩下的是一个回文串。利用这一条性质,我们可以把所有串插入一个Trie中,并且每一个节点维护两个值 \(v1\) 表示以该节点结尾的字符串个数, \(v2\) 表示以该节点为根的子树中又多少个回文串。

我们用一个字符串( \(s_j\) )的反串去Trie中查找,那么每到达一个节点,如果 \(s_j\) 的反串剩下的部分是一个回文串,那么答案加上该节点的 \(v1\) ,到达最后位置后(若没有最后位置,中途跳出),加上该节点的 \(v2\)

以上的实现需要知道一个串的后缀是不是回文串,可以考虑使用Manacher或者扩展KMP,因为Manacher需要把字符串中增加‘$’号,所以相对而言,用扩展KMP更方便一些。

扩展KMP又叫ZBOX,用来求一个字符串每一个后缀与整个字符串的LCP,实现过程和Manacher差不多。此题中可以对反串做一遍扩展KMP,再用正串对反串做一边扩展KMP,求出正串每一个后缀和整个反串的LCP,然后就可以 \(O(1)\) 判断是否是回文串了。

这个题目貌似需要卡一卡常数,开始的时候扩展KMP写错了(i从0开始的),导致一直TLE,而我却一直再卡常数…… 好吧代码中还有很多卡常数遗留下来的东西,大家凑合着看看吧……