6671：Str

题目描述

对于一个字符串 $s$，定义 $rev(s)$ 为它的反串，$abc$ 的反串为 $cba$。
有 $n$ 个串，第 $i$ 个串为 $s[i]$。

1. 先决定一个整数 $k~(1\leq k \leq n)$ (这一步有 $n$ 种方案)
2. 有序地从 $n$ 个串中，选出 $k$ 个串，设第 $i$ 个选择的串为 $t[i]$（这一步有 $A_{n}^{k}$ 种方案）
3. 对于每个串我们可以决定是否翻转它，如果翻转第 $i$ 个串，那么 $t[i]=rev(t[i])$。（这一步有 $2^k$ 种方案）

求有多少种方案使得 $str = t[1]+t[2]+...+t[k]$ ($+$ 表示字符串拼接) 是回文串。

输入解释

第一行输入一个整数 $T$，代表 $T~(1 \leq T \leq 20)$ 组数据。
对于每组数据，第一行一个数字 $n~(1\leq n \leq 10)$，表示串的个数，接下来 $n$ 行，第 $i$ 行表示字符串 $s[i]$。
输入保证，$n \geq 5$ 的数据不超过 5 组，每组数据字符串长度之和不会超过 1000。

输出解释

输出 $T$ 行，每行一个整数表示答案。

输入样例

2
2
a
a
2
a
ab

输出样例

12
6

样例描述
样例1有 s1,rev(s1),s2,rev(s2),s1+s2,s1+rev(s2),rev(s1)+s2,rev(s1)+rev(s2),s2+s1,s2+rev(s1),
rev(s2)+s1,rev(s2)+rev(s1) 一共 12 种。

样例2有 s1,rev(s1),s2+s1,s2+rev(s1),s1+rev(s2),rev(s1)+rev(s2) 共 6 种。

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2019 年百度之星·程序设计大赛 - 初赛一

源链接： HDU-6671

最后修改于 2020-10-25T23:33:21+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	131072/131072K(Java/Others)