Bovine Genomics

题目描述

农夫约翰拥有 $N$ 头有斑点的奶牛和 $N$ 头没有斑点的奶牛。刚刚完成一门牛基因学课程后，他坚信奶牛身上的斑点是由牛基因组中的突变导致的。

农夫约翰不惜代价对奶牛的基因组进行了测序。每个基因组都是一个长度为 $M$ 的字符串，由四个字符 A、C、G、T 构成。当他把奶牛的基因组对齐排列时，会得到如下表格（这里以 $N=3$ 为例）： Positions: 1 2 3 4 5 6 7 ... M

Spotty Cow 1: A A T C C C A ... T Spotty Cow 2: G A T T G C A ... A Spotty Cow 3: G G T C G C A ... A

Plain Cow 1: A C T C C C A ... G Plain Cow 2: A G T T G C A ... T Plain Cow 3: A G T T C C A ... T

仔细观察这张表后，他推测位置 2 和 4 足以解释斑点性状。也就是说，只要查看这两个位置上的字符，农夫约翰就能预测哪些奶牛有斑点、哪些没有（例如，如果他看到的是 G 和 C，那么这头牛一定是有斑点的）。

农夫约翰坚信，斑点性状不仅能由基因组中的一两个位置解释，而是可以通过查看三个互不相同的位置组成的集合来解释。请帮助他统计：有多少个由三个互不相同的位置构成的集合，能够分别解释斑点性状。

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

请输出能够解释斑点性状的、由三个互不相同的位置组成的集合数量。若仅通过查看基因组中这三个位置，就能在农夫约翰的牛群中以完全准确的方式预测斑点性状，则称这组三个位置能够解释斑点性状。

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

题目来源：Brian Dean

标签: USACO|2017|Silver

USACO|2017|Silver