#P2456. [SDOI2006] 二进制方程
[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组解。