#P2919. [Poi1998]Word equations

    ID: 2040 传统题 1000ms 512MiB 尝试: 41 已通过: 9 难度: 5 上传者: 标签>CF1700普及+/提高-普通并查集路径压缩按大小合并乘法原理高精度乘法

[Poi1998]Word equations

题目描述

一个非空的 0,10,1 元素的序列称作一个二进制单词。一个单词等式是一个形式为 x1,x2,⋯ ,xl=y1,y2,⋯ ,yrx_1,x_2,\cdots,x_l=y_1,y_2,\cdots,y_r 的等式,xix_i 和 yjy_j 是二进制数字(00 或 11)或者为变量的英文小写字母。对于每个变量代替一个固定长度的二进制单词,这个长度称作变量的长度。为了解决一个单词等式我们必须给所有的变量分配适当长度的二进制单词(分配给变量 xx 的单词长度必须等于这个变量的长度)。采用这种方式,如果用变量代替单词,那么等式的两边(替换后的二进制单词)相等。

对于一个给定的等式,计算它有多少种不同的方法使等式成立。

例如:a,b,c,d,ea,b,c,d,e 是变量,它们的长度分别是 4,2,4,4,24,2,4,4,2,(即 aa 的长度是 44,bb 的长度是 22,⋯\cdots )。

考虑等式:1bad1=acbe\text{1bad1}=\text{acbe}

这个等式有 1616 种不同的方法能使等式成立。

求每个等式的不同解的数量。

输入格式

第一行有一个整数 xx,表示等式的总数。

下面的行包含 xx 个等式的描述,每个等式的描述包含 66 行,描述的等式间没有空行,每个等式的描述是:

  • 第一行有一个整数 kk,表示等式中不同变量的个数,并且假定是用英文字母表中的前 kk 个小写字母;
  • 第二行有 kk 正整数,它们由空格分开,代表等式中 kk 个变量的长度;
  • 第三行有一个整数 ll,表示等式左边二进制单词的长度,这个长度包括 00、11、及变量;
  • 第四行是等式左边的二进制单词;
  • 第五行有一个整数 rr,表示等式右边二进制单词的长度;
  • 第六行是等式右边的二进制单词。

对等号的每一侧,把每个变量出现的位置都展开为它所代表的二进制单词,展开后的长度各自不超过 10410^4。这 kk 个变量均至少出现一次。若 k=0k=0,给出变量长度的第二行为空。

输出格式

对于每个等式,输出一行整数,表示不同解的精确数量。

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

数据规模与约定

对于 100%100\% 的数据,1≤x≤51\le x\le 5,0≤k≤260\le k\le 26。

题目来源