# P3449 [POI2006]PAL-Palindromes

• 74通过
• 133提交
• 题目提供者 洛谷
• 评测方式 云端评测
• 标签 哈希,HASH 字典树,Trie树 POI 2006 高性能
• 难度 省选/NOI-
• 时空限制 1000ms / 384MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目描述

Little Johnny enjoys playing with words. He has chosen $n$ palindromes (a palindrome is a wordthat reads the same when the letters composing it are taken in the reverse order, such as dad, eye orracecar for instance) then generated all $n^2$ possible pairs of them and concatenated the pairs intosingle words. Lastly, he counted how many of the so generated words are palindromes themselves.

However, Johnny cannot be certain of not having comitted a mistake, so he has asked you to repeatthe very same actions and to give him the outcome. Write a programme which shall perform thistask for you.

reads the palindromes given by Johnny from the standard input, determines the number of words formed out of pairs of palindromes from the input, which are palindromes themselves, writes the outcome to the standard output.

给出n个回文串s1, s2, …, sn 求如下二元组(i, j)的个数 si + sj 仍然是回文串 规模 输入串总长不超过2M bytes

## 输入输出格式

输入格式：

The first line of the standard input contains a single integer $n$, $n\ge 2$, denoting the number ofpalindromes given by Johnny. The following $n$ lines contain a description of the palindromes. The $(i+1)$'st line contains a single positive integer $a_i$ denoting the length of $i$'th palindrome and apalindrome of $a_i$ small letters of English alphabet. The number $a_i$ is separated from the palindromeby a single space. The palindromes in distinct lines are distinct. The total length of all palindromesdoes not exceed $2\ 000\ 000$.

输出格式：

The first and only line of the standard output should contain a single integer: the number of distinctordered pairs of palindromes which form a palindrome upon being concatenated.

## 输入输出样例

输入样例#1： 复制
6
2 aa
3 aba
3 aaa
6 abaaba
5 aaaaa
4 abba
输出样例#1： 复制
14
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。