BZPRO

#2919. [Poi1998]Word equations

内存限制：128 MiB 时间限制：1 Sec
提交 提交记录 讨论

题目描述

    每个非空的0，1元素的序列称作一个二进制单词。一个单词等式是一个形式为X1X2…XL＝Y1Y2…YR的等式，XI和YJ是二进制数字（0或1）或者变体的英文小写字母（即通常我们所说的变量）。对于每个变体代替一个固定长度的二进制单词，这个长度称作变体的长度。为了解决一个单词等式我们必须给所有的变体分配适当长度的二进制单词（分配给变体X的单词长度必须等于这个变体的长度）。采用这种方式，如果用变体代替单词，那么等式的两边（替换后的二进制单词）相等。
    对于一个给定的等式，计算它有多少种不同的方法使等式成立。
例如：A，B，C，D，E是变体，它们的长度分别是4，2，4，4，2，（即A的长度是4，B的长度是2，……）；考虑等式：1BAD1＝ACBE
    这个等式有16种不同的方法能使等式成立。
【任务】编写程序：
１、            读入等式的总数及它们的描述；
２、            寻找对于每个等式最多有多少种不同方法使等式成立；
３、            将结果输出

输入格式

 第一行有一个整数X，1≤X≤5，表示等式的总数。下面的行包含X个等式的描述，每个等式的描述包含6行，描述的等式间没有空行，每个等式的描述是：第一行有一个整数K，0≤K≤26，表示等式中不同变体的个数，并且假定是用英文字母表中的前K个小写字母；第二行有K个正整数，它们由空格分开，代表等式中K个变体的长度；第三行有一个整数L，表示等式左边二进制单词的长度，这个长度包括0、1、及变体；第四行是等式左边的二进制单词；第五行有一个整数R，表示等式右边二进制单词的长度；第六行是等式右边的二进制单词。在等式两边的二进制单词的长度总和不超过10000。

输出格式

    对于每个I，1≤I≤X，你的程序应该在输出文件PRO．OUT的第I行上写出第I个等式有多少种不同的方法使等式成立。

样例

样例输入


			
1                                         

5

4 2 4 4 2

5

1BAD1

4

ACBE

样例输出


			
 16

数据范围与提示

BZPRO Powered by Remmina.
Github Repository