P15198 [SWERC 2018] Crosswords

为了吸引更多游客来到巴黎，Anne 计划在卢浮宫的外墙举办一场盛大的声光秀。外墙上有多层窗户，且窗户在垂直方向上对齐。因此，Anne 想到通过窗户展示巨型字母，每个窗户一个字母，从而同时在水平和垂直方向上形成单词。 在给定的外墙上，窗户排列成一个 $N$ 行 $M$ 列的矩形网格。Anne 收集了一个包含 $A$ 个 $N$ 字母单词的列表和一个包含 $B$ 个 $M$ 字母单词的列表。她想知道有多少种方式在该网格上同时水平显示 $N$ 个长度为 $M$ 的单词和垂直显示 $M$ 个长度为 $N$ 的单词。

输入包含以下内容： - 第一行包含两个整数 $N$ 和 $A$，用一个空格分隔。 - 第二行包含两个整数 $M$ 和 $B$，用一个空格分隔。 - 接下来的 $A$ 行包含 $N$ 字母单词，每行一个。 - 接下来的 $B$ 行包含 $M$ 字母单词，每行一个。

输出应包含一行，内容为一个整数，表示不同单词网格的总数。

#### 样例解释 1 解决方案如下： | s | a | y | s | |:-:|:-:|:-:|:-:| | a | r | e | a | | t | e | s | t | | w | a | y | s | |:-:|:-:|:-:|:-:| | a | r | e | a | | r | e | s | t | #### 样例解释 2 解决方案如下： | i | t | s | |:-:|:-:|:-:| | t | h | e | | s | e | t | | r | a | n | |:-:|:-:|:-:| | a | g | o | | n | o | w | ### 数据范围 输入满足 $2 \leq N, M \leq 4$ 且 $1 \leq A \times B \leq 1008016$。 单词来自英语词典。两个列表中的单词均不重复。单词由 `'a'`（ASCII 码 97）到 `'z'`（ASCII 码 122）的小写字母组成。 第一个列表中的单词将垂直显示，从上到下。第二个列表中的单词将水平显示，从左到右。同一个单词可以在构建网格时多次使用，即如果它属于第一个（或第二个）单词列表，它可以出现在多个列（或行）中。 当 $N = M$ 时，不允许将第一个列表中的单词水平使用（除非它们也出现在第二个列表中），也不允许将第二个列表中的单词垂直使用（除非它们也出现在第一个列表中）。 翻译由 DeepSeek 完成