#1479. 小学数学题 加强版

小学数学题 加强版

题目描述

本题是杭州学军中学“图灵杯”网络邀请赛题目加强,注意有改动。

小学生 zzq 喜欢做小学数学题。一天,他在口算题卡上发现了这样一道题:有算式 ABC+DBC=BCEABC+DBC=BCE,求出任何一个解。zzq 想了想,求出了一个解 124+124=248124+124=248A=1,B=2,C=4,D=1,E=8A=1,B=2,C=4,D=1,E=8)。zzq 又看了一眼题目,发现要求 D1D\neq 1,所以 zzq 只好又求出了一个解 137+237=374137+237=374A=1,B=3,C=7,D=2,E=4A=1,B=3,C=7,D=2,E=4)。

zzq 觉得这类题目很有意思,因此希望你解决一些这样的问题。每个问题都形如「一个非空大写字母串 ++ 一个非空大写字母串 == 一个非空大写字母串」,其中每个大写字母代表一个数位,相同的大写字母代表相同的数位,不同的大写字母也可以代表相同的数位。此外,我们要求将字母替换为数位后等式成立,且被加数和结果均大于 0\mathbf 0,且没有前导零。我们还可能有一些限制条件,限制条件形如某个大写字母不代表某个数位。

对于这样的一个问题,你需要求出可能的解的个数。解即实际的等式(如 124+124=248124+124=248)。答案对 2312^{31} 取模。

输入格式

第一行为一个字符串,即算式。

接下来一行一个非负整数 mm,表示限制条件的个数。

接下来 mm 行每行 a,ba,baa 为某个大写字母,bb 为某个数位,表示 aa 这一字母不能等于 bb

输出格式

输出解的个数。由于这个值可能较大,对 2312^{31} 取模。

样例 1

A+B=C
2
B 2
C 5
26
PLOTS+ACTOR=FILMS
6
R 2
A 3
N 4
D 5
O 6
M 7
213880

数据范围与提示

对于所有数据,m10000m\le 10000。下述的算式长度即输入第一行字符串的长度。

Subtask 1120pts20\,\mathrm{pts}):算式长度不超过 55

Subtask 2220pts20\,\mathrm{pts}):算式长度不超过 1717

Subtask 3320pts20\,\mathrm{pts}):算式长度不超过 2020

Subtask 4420pts20\,\mathrm{pts}):算式长度不超过 2323

Subtask 5520pts20\,\mathrm{pts}):算式长度不超过 2626

目前的数据很弱,欢迎 hack,如果没有管理员权限可以发帖。