#P2456. [SDOI2006] 二进制方程

    ID: 1464 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选山东2006进制高精度字符串

[SDOI2006] 二进制方程

题目描述

一个形如:

X1X2…Xn=Y1Y2..Ym

的等式称为二进制方程。

在二进制方程的两边:Xi和Yj (1<=i<=n;1<=j<=m)是二进制数字(0、1)或者一个变量(小写字母)。每个变量都是一个有固定长度的二进制代码,他可以在等式中取代变量的位置,称这个长度为变量的长度。为了解一个二进制方程,需要给其中的变量赋予适当的二进制代码,使得我们用他们替代等式中的相应的变量后(等式的两边都变成二进制代码),这个等式成立。

编程任务:

对于每一个给出的方程,计算一共有多少组解。已知变量最多有26个(26个英文小写字母),且等式的每一端的数字和变量的长度之和不超过10000。

输入格式

第一行:k(k<=26,变量的个数,规定使用小写英文字母中的前k个字母作为变量,如k=5,则变量a,b,c,d,e)。

第二行:k个正整数,中间用一个空格隔开,依次代表k个变量的长度。

第三行:等式左边的表达式。

第四行:等式右边的表达式。

输出格式

等式中出现的变量共有多少组解。

2
4 2
1b1
a
4
5
4 2 4 4 2
1bad1
acbe
16

提示

样例一:4组解

1 、a=1001; b=00

2、 a=1011; b=01

3、 a=1101; b=10

4、 a=1111; b=11)

样例二:K=5,变量:a,b,c,d,e。长度分别为:4 2 4 4 2。等式是:1bad1= acbe

输出16,即变量a,b,c,d,e共有16组解。