这题和NOI那道向量内积一个套路
首先考虑求两行的不同元素个数,可以转化成一个行向量(a)和列向量(b)相乘得到一个值.如果只有(A,C)两种字符,那么令对应权值(A=1,C=-1),然后这两行的不同元素个数可以表示成(frac{m-ab}{2}),拓展到四个字符的情况,那么就搞三种形式,分别为(A=C=1,G=T=-1|A=1,C=-1,G=T=0|A=C=0,G=1,T=-1),记对应的行向量为(a1,a2,a3),列向量为(b1,b2,b3),那么他们的不同元素个数应该是(frac{3m-(a1b1+2a2b2+2a3b3)}{4})
如果每次暴力比较,复杂度也就是跟普通暴力一样的.所以考虑把所有行的行向量加起来,然后乘上要比较的那一行的列向量,如果这一行是答案要求的,那么得到的值应该是((n-1)k).不过如果得到的结果是((n-1)k),这一行有可能并不是答案.为了避免这种情况,不妨给每一行随机一个权值(w_i),使得任何一行和这一行匹配得出的值要乘以(w_i),那么答案行(ans)的列向量乘以行向量之和的结果就应该是(sum_{i eq ans} w_i k).这样枚举每一行,然后用对应列向量乘行向量之和check就行了
细节看代码吧实在是懒得写了