logo AlgoBeat OnlineJudge
登录 注册

#102911. [BZOJ 2911] [Poi1997]The Number of Symmetrical Choices

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定两个单词序列:。我们每次从两个序列中选取 中的一个,将被选择的单词将从左到右进行合并。共做 次选择。每一步我们都可以从两个序列中的任意一个拿走一个单词。也就是说:最终的选择都是由 组成的一个长度为 的序列。当然不同选择方式,最终可能组成同一个单词。

如果一个选择的结果是可逆的,则我们说这种选择是对称的选择。例如:一个单词从左到右和从右到左读都相同。

你需要写一个程序来计算对称选择的数目。

输入格式

第一行是一个正整数 ,下面 行是连续的第一个序列,其中每一行为一个单词 ,接下来是第二个序列,每一行为一个单词

单词全部由小写的英文字母组成。

输出格式

输出非负整数,为对称选择的数目。

样例

样例输入 #1

5
ab
a
a
ab
a
a
baaaa
a
a
ba

样例输出 #1

12

数据范围与提示

对于 的数据, 单词的长度