First, we can treat sequences that differ in the position of their first \(1\) as separate problems. This is because the position of the first \(1\) does not change through the operation described in the problem statement, so such sequences will never become identical through operations. From here on, let’s proceed under the assumption that \(A_{i, 1} = 1\).

(The following observations can be discovered through experiments or polynomial considerations.)

We can define the inverse operation for the operation given in the problem statement. Therefore, if we consider a graph where the length-\(M\) binary sequences starting with \(1\) are vertices, and the operations correspond to edges, this graph is a collection of cycles. In fact, the following holds:

• For every sequence, by performing the operation several times, it is possible to turn all elements at positions represented as the \((2^x + 1)\)-th element using a non-negative integer \(x\) into \(0\). (We call this the “standard form.”)

This can be proved by using Lucas’s theorem, among other methods. As a natural consequence, the length of each cycle is \(2^m\), where \(m\) is the smallest non-negative integer such that \(2^m + 1 \leq M\).

The flow of the solution to this problem is as follows: First, perform operations on all sequences until they reach their standard forms, and compute the number of operations required up to that point. Then, consider the problem for each standard form.

For each \(i = 1, 2, \dots, N\), compute the standard form of sequence \(A_i\) and the cost required to reach the standard form. Note that the considerations about the cycle length mentioned above hold even if we take any prefix of \(A_i\). Proceeding with \(x = 0, 1, 2, \dots\) in order, we only need to perform the operation \(2^x\) times to turn \(A_{i, 2^x + 1}\) into \(0\) if \(A_{i, 2^x + 1} = 1\).

The remaining task is to solve the problem for each standard form. In other words, we have an integer sequence \(B\), and we need to compute \(\displaystyle \sum_{i=1}^{m} \sum_{j=i}^{m} \left( (B_j - B_i) \bmod 2^m \right)\). This can be computed using a Segment Tree or similar data structures.

The bottleneck in terms of computational complexity is the part where we compute the standard forms. Performing multiple operations can be done using FFT, but if we do it every time, we might not meet the time limit. In practice, we don’t need to actually perform the operation each time; it suffices to keep track of the number of times the operation has been performed, which allows us to determine the value at a given position in \(O(M)\) time. If this solution is implemented, the overall computational complexity is \(O(NM \log NM)\).