まず、最初の \(1\) の位置が違うような数列同士は別の問題として扱って構いません。なぜなら、問題文にある操作で最初の \(1\) の位置は変わらないので、そのような数列は操作によって一致することがないからです。これ以降、 \(A_{i, 1} = 1\) として解説します。

(以下の考察は、実験もしくは多項式的な考察によって発見できます)

問題文にある操作には逆操作を定義できます。よって、最初の要素が \(1\) であるような、長さ \(M\) の各要素が \(0, 1\) からなる整数列を頂点とし、操作を辺に対応付けたグラフを考えると、これはいくつかのサイクルの集合になっています。実は以下のことが成り立ちます。

• 全ての数列は、何度か操作をすることで、非負整数 \(x\) を用いて \(2^x + 1\) 番目と表される要素を全て \(0\) にできる。(これを “標準形” と呼ぶ)

これは Lucas の定理を用いるなどして証明できます。自然な帰着として、全てのサイクルの長さは \(2^m + 1 \leq M\) であるような最小の非負整数 \(m\) を用いて \(2^m\) です。

本問題の解法の流れとしては、まず全ての数列を標準形になるまで操作し、そこまでにかかった操作回数を求めます。その後標準形ごとの問題を考えます。

\(i = 1, 2, \dots ,N\) についてそれぞれ、数列 \(A_i\) の標準形と標準形にするまでにかかるコストを求めます。上で書いたサイクルの長さについての考察は、 \(A_i\) の任意の prefix を取り出しても同様に成り立つことに注意します。\(x = 0, 1, 2, \dots\) と順に、もし \(A_{i, 2^x + 1} = 1\) なら \(A_{i, 2^x + 1} = 0\) にするために \(2^x\) 回操作をするだけでよいです。

残りは標準形ごとの問題を解きます。これはつまり、整数列 \(B\) があるので \(\displaystyle \sum_{i=1}^{m} \sum_{j=i}^{m} \left ((B_j - B_i) \bmod 2^m \right )\) を求めよという問題で、 Segment Tree などを用いれば解けます。

計算量がネックになるのは標準形を求める部分です。操作を複数回行うこと自体は FFT でできますが、毎回実行していると TL に間に合わないかもしれません。実際には毎回実際に操作をする必要はなくて、操作をした回数だけ持っておけばある位置の値を \(O(M)\) で求められるので十分です。以上の解法を実装すれば、全体の計算量は \(O(NM \log NM)\) になります。

\(\text{mod } 2\) だけでなく一般の素数 \(P\) について \(\text{mod } P\) でも、同じような解法で解くことができます。