P3670 [USACO17OPEN] Bovine Genomics S

题目描述

Farmer John 拥有 $N$ 头有斑点的牛和 $N$ 头没有斑点的牛。他刚刚完成了一门关于牛遗传学的课程，并确信他牛身上的斑点是由牛基因组中的突变引起的。

Farmer John 花费巨资对他的牛进行了基因组测序。每个基因组是一个由字符 A、C、G 和 T 组成的长度为 $M$ 的字符串。当他将牛的基因组排列起来时，会得到如下表格，这里展示的是 $N=3$ 的情况：

位置：1 2 3 4 5 6 7 ... M

斑点牛 1：A A T C C C A ... T  
斑点牛 2：G A T T G C A ... A  
斑点牛 3：G G T C G C A ... A  

普通牛 1：A C T C C C A ... G  
普通牛 2：A G T T G C A ... T  
普通牛 3：A G T T C C A ... T 

仔细观察这个表格后，他推测位置 2 和 4 足以解释斑点现象。也就是说，通过仅查看这两个位置的字符，Farmer John 可以预测哪些牛是有斑点的，哪些是没有斑点的（例如，如果他看到 G 和 C，这头牛一定是有斑点的）。

Farmer John 确信，斑点现象不仅仅可以通过基因组中的一个或两个位置来解释，而是可以通过查看三个不同的位置来解释。请帮助他计算能够解释斑点现象的三个不同位置集合的数量。

输入格式

输入的第一行包含 $N$（$1 \leq N \leq 500$）和 $M$（$3 \leq M \leq 50$）。接下来的 $N$ 行每行包含一个长度为 $M$ 的字符串，这些字符串描述了斑点牛的基因组。最后的 $N$ 行描述了普通牛的基因组。

输出格式

请计算能够解释斑点现象的三个不同位置集合的数量。如果通过查看基因组中这三个位置的字符，可以在 Farmer John 的牛群中完美准确地预测斑点性状，那么这个三个位置的集合就解释了斑点现象。

输入输出样例 1

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

22