ARC115 A Two Choices
同じものを答えているところはどうやっても正解数が変わらないので考えなくてよい.
異なる部分の個数が奇数個のとき, どうやっても正解数を一緒にできない. よって奇数個となるようなペアの個数を求めればよい. しかし全ペアについて試すと間に合わない.
ここで各文字列について$ 1の個数を考えると, その偶奇を調べればよいとわかる(これはエスパーしてもよいが, mod2を考えたり同じ文字列内において文字と文字を交換しても異なる部分の個数が変わらないことを示したりすることから導ける). よって, $ 1の個数が(偶数のものの個数)×(奇数のものの個数) が答えとなる. 計算量は$ O(NM)となる.