#P18586. P-P-Palindrome
P-P-Palindrome
P-P-Palindrome
给定 个只含小写英文字母的字符串 。
统计满足以下条件的有序对 的数量:
- 均为非空回文串。
- 和 各自至少在某个给定字符串中作为连续子串出现。它们可以来自不同的字符串。
- 将 接在 后面得到的 也是回文串。
这里回文串是指从左到右与从右到左读完全相同的字符串。
两个有序对不同,当且仅当它们的 不同或 不同;同一个字符串出现多次不产生新的选择。允许 ,且不要求 在输入中出现。
输入格式
第一行一个整数 。
接下来 行,每行一个非空字符串,第 行为 。
输出格式
输出一个整数,表示满足要求的不同有序对数量。答案不取模。
数据范围
,,。输入只包含一组数据。
样例输入 1
2
aaaa
aaa
样例输出 1
16
样例输入 2
3
abaaa
abbbba
bbbaba
样例输出 2
28
样例说明
第一组可选择的回文串为 a、aa、aaa、aaaa。任取两个拼接后仍为回文串,共有 个有序对。