(注)　他の解法の方が高速で実装も楽だと思います

まずは以下の2つのTLE解法をご覧ください。

TLE解法 1

サイズ \(NM\) の bitset を用意します。

\(j = 1, 2, ..., M\) について以下を行います。

\(x = 1, 2, ..., 999\) について \(A[i][j] = x\) となるような \(i\) のかたまりを作ります。それぞれの \(i\) について、そのかたまりと一対一の対応が取れている数値の場所の bit を立てます。

最後に、それぞれの数列のペアについて、bitset の \(\text{AND}\) を取ると、共通するかたまりが抽出できます。最後に、立っているビットの個数が奇数であれば、その \(2\) つの数列は似ていることになります。ビットサイズは \(NM\) 必要で、それぞれの数列のペアについて演算するため、 \(W=64\) として、計算量は \(O(\frac{N^3 M}{W})\) となります。

TLE解法 2

\(N \times N\) の配列を用意し、数列のペアにおける、問題文中の個数の偶奇を保管することにします。

上述のかたまり内のそれぞれのペアについて偶奇を反転させます。

最悪ケースは例えば \(A_{i, j}\) がすべて等しいようなケースで、 計算量は \(O(N^2 M)\) となります。

AC 解法

以上 2 つのTLE解法を組み合わせることでこの問題を解くことができます。

TLE解法 1 は、かたまりの大きさが \(2\) 以上のもののみ考慮することで必要なビットサイズを半分にできる、ということが考えられます。これを応用して、あるしきい値 \(B\) 以上のときのみ考慮してみましょう。かたまりは高々 \(NM/B\) 個となり、必要なビットサイズは \(1/B\) 倍となります。計算量は \(O(\frac{N^3 M}{WB})\) です。

しかし、これでは \(B\) 未満のときにどうするかが課題です。そこで、\(B\) 未満のときはTLE解法 2 の処理をしてみましょう。そして、最終的にそれぞれのTLE解法で偶奇が異なれば、その2つの数列は似ている、とできます。大きさ最大 \(B\) のものが \(NM/B\) 個あるときが最悪ケースとなり、計算量は \(B^2 \times NM/B \) で \(O(NMB)\) となります。

以上より、計算量は \(O(\frac{N^3 M}{WB} + NMB)\) となり、これを最小化させるためには \(B=N/\sqrt{W}\) とすればよく、全体で\(O(\frac{N^2 M}{\sqrt{W}})\)となります。\(\frac{N^2 M}{\sqrt{W}}\) はそのまま計算すると \(10^9\) となり、本問題はbayashikoさんのユーザ解説にあるように処理が軽いため、間に合います。

実装例 (C++, 857 ms)

実装例 (C++, pragmaによる高速化後, 590 ms)