bzoj#P1524. [POI2006]Pal

[POI2006]Pal

题目描述

Johnny 喜欢玩文字游戏。

他写下了 nn 个回文串,随后将这些串两两组合,合并成一个新串。容易看出,一共会有 n2n^2 个新串。

两个串组合时顺序是任意的,即 ab 可以组合成 abba,另外自己和自己组合也是允许的。

现在他想知道这些新串中有多少个回文串,你能帮帮他吗?

输入格式

第一行一个整数 nn

接下来 nn 行,第 ii 行包含一个数 aia_i 和一个长度为 aia_i 的回文串。

保证所有串只包含小写字母,且所有串两两不同,所有回文串的长度和不超过 2×1062 \times 10^6

输出格式

输出一个整数,代表满足条件的新串的数量。

6
2 aa
3 aba
3 aaa
6 abaaba
5 aaaaa
4 abba
14