[POI1998]单词等式

Grade 0 Open Time Tuesday, 22 January 2013, 9:40 am
Discount 0.8 Time Discount Tuesday, 22 January 2013, 9:40 am
Allow late Yes Close Time Tuesday, 22 January 2013, 9:40 am
Input file row.in Output file row.out

所有非空的01序列被称作一个二进制单词。一组相等的单词是如下形式的等式:x1x2..xl=y1y2..yr ,这里xi 和yj 是二进制字符01或是用小写字母表示的变量。对每一个变量都有一个固定长度的两进制单词来代替这个变量,这个长度称之为这个变量的长度。为了解决单词相等 的问题我们需要用某种方法分配给所有变量适当的二进制单词(这个二进制单词的长度必须为这个变量的长度),使得变量被取代后的等式成立。对一个给定的等式 计算有几种解答。

例子:

让a,b,c,d,e分别为长度为4,2,4,4,2的5个变量。考虑以下等式:1bad1=acbe。这个等式有16种不同的解答方案。

任务:

写一个程序:

  • 从文件中读入等式的数目以及它们的描述。
  • 对每个等式找出它们的解答方案数。
  • 将结果写入文件。

输入:

在文件的第一行有一个整数x(1<=x<=5)表示等式的数目,随后有x个等式的描述。每个描述包括6行,两个等 式的描述之间没有空行。每个等式用以下方式描述:在描述的第一行有一个整数k(0<=k<=26)表示等式中不同的变量数目,我们假设变量是 从a起的k个小写字母。第二行有k个由空格隔开的正整数,表示k个变量的长度(第一个数表示a的长度,第二个数表示b的长度)。第三行有一个整数l,表示 等式左边的长度(有0 1及变量(单个字母)组成的单词长度)。等式左边将被写在下一行,仅包括01及小写字母而没有空格。以下两行给出了对等式左边的描述,第一行为一个正整数 r,表示等式右边的长度,等式的右边被写在第二行。等式两边所有变量的和相等且不超过10000。

输出:

对每个I (1<=I<=x),你的程序必须在第I行给出第I个等式的不同解答方案数,并将它写入文件。

输入样例:

1
5
4 2 4 4 2
5
1bad1
4
acbe

输出样例:

16