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

无

无