QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 6172. 加法方程问题

统计

埃及是世界上文化发达最早的几个地区之一。古埃及数学取得了较高的成就,从现今遗留下来的古埃及数学纸草文献“莫斯科纸草书”和“兰德纸草书”等可看出,古埃及人的数学知识包括算术、代数和几何三个方面。埃及很早就用十进记数法,他们能解决一些加法方程的问题,并有等差、等比数列的初步知识。

设 $A$ 和 $B$ 是两个由英文小写字母组成的字符串。字符串集合 $S$ 是由 $n$ 个字符串组成的集合,其中每个字符串均由英文小写字母组成。从集合 $S$ 中选取一个字符串 $C$,它与字符串 $A$ 和 $B$ 共同组成如下加法表达式:

$$A+B=C$$

其中字符串 $A$、$B$ 和 $C$ 均按位右对齐。

例如:当 $A=\texttt{ab}$,$B=\texttt{ac}$ ,以及 $C=\texttt{da}$ 时,相应的加法表达式为:

$$\texttt{ab} + \texttt{ac} = \texttt{da}$$

这个表达式建立了一个加法方程。如果用数字 $0\sim 9$ 来替换表达式中的小写字母,使得该表达式成为一个正确的 $10$ 进制加法竖式计算式,则称这样的替换为该加法方程的一个解。

例如:$a=1,b=4,c=7,d=3$ ,是上述加法方程的一个解。

显然,一个加法方程可以有多个不同的解。为了明确起见,对于一个加法方程的规范解做如下规定:

  1. 表达式中出现的所有英文小写字母均与 中的一个数字一一对应,即相同字母对应于相同的数字,不同字母需对应于不同的数字。
  2. 解中所有英文小写字母不重复地出现恰好一次。
  3. 解中英文小写字母在表达式中出现至少1次。
  4. 表达式中字符串首字母对应的数字不能为 $0$,即便字符串长度为 $1$ 也不行。

满足规定的解称为相应加法方程的一个规范解。当同一个加法方程的两个规范解中至少有一个字符所对应的数字不同时,称这两个规范解是不同的规范解。

加法方程问题:对于给定的字符串 $A$、$B$ 和 $C$,假设它们所对应的加法方程有 $x$ 个规范解,要判断 $x$ 对自然数 $m$ 取模是否为 $k$

输入格式

输入的第一行包含一个字符串 $A$。

接下来一行,包含一个字符串 $B$。

接下来一行,包含三个整数 $n, m, k$。

接下来 $n$ 行,每行一个字符串 $S_i$,描述 $S$ 中的一个字符串。

输出格式

输出 $n$ 行,每行一个字符串 YESNO,表示如果 $C=S_i$,那么它们所对应的加法方程是否满足要求。

样例数据

样例输入

abc
efbe
7 3 2
dcbc
fbed
bcdd
bdga
abdb
fedc
ghijk

样例输出

NO
NO
YES
YES
NO
NO
NO

子任务

记 $s$ 表示每个字符串长度的最大值:

测试点编号 $s$ $n$ $m$ $k$
$1 \sim 3$ $1 \leq s \leq 10$ $ 1 \leq n \leq 100$ $m = 3628801$ $k = 1$
$4 \sim 7$ $1 \leq s \leq 15$ $ 1 \leq n \leq 80\,000$ $2 \leq m \leq 1\,000$ $1 \leq k < m$
$8 \sim 10$ $ 1\leq n \leq 100\,000$