This explanation generally uses \(0\)-based indexing.

For the inversion number of a binary sequence \(Y = (Y_{0}, Y_{1}, \dots, Y_{|Y|-1})\), the following holds:

• If there are \(P\) indices \(i\) where \(Y_{i} = 0\), and the sum of such indices is \(Q\), then the inversion number of \(Y\) is \(Q - \frac{P(P-1)}{2}\).

Therefore, we need to find the number of zeros in \(B\) and the sum of their indices.

Here, we define a sequence of sequences \(C = (C_{0}, C_{1}, \dots, C_{M-1})\) as follows:

• \(C_{i} = (C_{i,0}, C_{i,1}, \dots, C_{i,K-1})\) is a sequence of length \(K\), where the \(j\)-th element \(C_{i,j}\) is equal to \(\operatorname{popcount}(j \operatorname{AND} A_{i})\).

Let \(P_{i}\) be the number of \(0\)s in \(C_{i}\), and \(Q_{i}\) be the sum of indices where \(C_{i}\) is \(0\). The inversion number of \(B\) can be expressed as:

\[\text{inversion}(B) = \sum_{i=0}^{M-1}(Q_{i}M + iP_{i}) - \frac{(\sum P)(\sum P - 1)}{2}\]

Thus, if we know \(P_{i}\) and \(Q_{i}\) for each integer \(i\) from 0 to \(M-1\), we can determine the answer.

To find \(P_{i}\) and \(Q_{i}\), we need the difference between the number of \(0\)s and \(1\)s in \(C_{i}\), and the difference between the sum of indices where \(C_{i}\) is \(0\) and where it is \(1\).

Here, we find an integer sequence \(Z\) such that \(K = \sum 2^{Z_{j}}\) and \(0 \leq Z_{0} < Z_{1} < \cdots < Z_{L-1} = N-1\), similarly to the way \(A\) is input.

Using \(Z\), we decompose the interval \([0, K)\) into \([0, 2^{Z_{L-1}}), [2^{Z_{L-1}}, 2^{Z_{L-2}} + 2^{Z_{L-1}}), \dots, [K - 2^{Z_{0}}, K)\), and consider the contribution of each segment to \(P_{i}\) and \(Q_{i}\).

For the numbers of \(0\)s and \(1\)s in the contiguous subsequence \((C_{i, K-2^{Z_{0}}}, C_{i, K-2^{Z_{0}+1}}, \dots, C_{i, K-1})\) in \(C_{i}\), the following holds:

• If \((A_{i} \operatorname{AND} (2^{Z_{0}} - 1)) \neq 0\), the difference is \(0\).
• If \((A_{i} \operatorname{AND} (2^{Z_{0}} - 1)) = 0\), all elements are equal to \(\operatorname{popcount}(A_{i} \operatorname{AND} (K - 2^{Z_{0}}))\).

For the sums of indices where \(C_{i}\) is \(0\) and where it is \(1\), the following holds:

• If \(\operatorname{popcount}(A_{i} \operatorname{AND} (2^{Z_{0}} - 1)) \geq 2\), the difference is 0.
• If \(\operatorname{popcount}(A_{i} \operatorname{AND} (2^{Z_{0}} - 1)) = 1\), the sum of indices where \(C_{i}\) is the remainder of \(\operatorname{popcount}(A_{i}\operatorname{AND}(K-2^{Z_{0}}))\) divided by \(2\) is smaller by \(2^{Z_{0}-1} \times (A_{i} \operatorname{AND} (2^{Z_{0}} - 1))\).
• If \(\operatorname{popcount}(A_{i} \operatorname{AND} (2^{Z_{0}} - 1)) = 0\), all elements are \(0\) or \(1\).

This gives us the contribution of the interval \([K - 2^{Z_{0}}, K)\) to \(P_{i}\) and \(Q_{i}\). We can similarly find the contributions of other intervals.

By not calculating these contributions separately for all \(Z\) but appropriately dividing the intervals and performing precomputations such as cumulative sums, we can compute \(P_{i}\) and \(Q_{i}\) in \(O(L_{i})\) time.

Specifically, if \(L_{i} \geq 2\), we divide the whole range into five intervals: \([0, R_{X_{i,1}+1}), [R_{X_{i,1}+1}, R_{X_{i,1}}), [R_{X_{i,1}}, R_{X_{i,0}+1}), [R_{X_{i,0}+1}, R_{X_{i,0}}), [R_{X_{i,0}}, K)\). Here, \(R_{a}\) is \(K\) minus the remainder of \(K\) divided by \(2^{a}\).

Since all \(P\) and \(Q\) can be computed in \(O(\sum L)\) time with appropriate precomputations, the answer to this problem can be obtained in linear time relative to the input.

C++ implementation example

Python implementation example:

MOD = 998244353

# input
N, M = map(int, input().split())
K = input()
X = [[] for i in range(M)]
for i in range(M):
    L, *X[i] = map(int, input().split())

# return l + (l + 1) + ... + (r - 2) + (r - 2) mod 998244353
def range_sum(l: int, r: int) -> int:
    return ((l + r - 1) * (r - l)) // 2 % MOD

# init
K = K[::-1]
k = [0] * (N + 1)
p2 = [1] * (N + 1)
inv2 = (MOD + 1) // 2
for i in range(N):
    p2[i + 1] = p2[i] * 2 % MOD
    if K[i] == '1':
        k[i] = p2[i]
for i in range(N, 0, -1):
    k[i - 1] = (k[i] + k[i - 1]) % MOD

# return diff number and sum index
def f(v: list[int]) -> tuple[int, int]:
    if len(v) == 0:
        return (k[0], range_sum(0, k[0]))
    sign = 0
    P = 0
    Q = 0
    ind = N
    if len(v) >= 2:
        for i in range(2, len(v)):
            if K[v[i]] == '1':
                sign ^= 1
        if K[v[1]] == '1':
            Q += (sign * 2 - 1) * inv2 * (k[v[1]] - k[v[1] + 1]) * p2[v[0]] % MOD
            sign ^= 1
        ind = v[1]
    Q += (sign * 2 - 1) * inv2 * (k[v[0] + 1] - k[ind]) * p2[v[0]] % MOD
    if K[v[0]] == '1':
        P += (1 - sign * 2) * (k[v[0]] - k[v[0] + 1]) % MOD
        Q += (1 - sign * 2) * range_sum(k[v[0] + 1], k[v[0]]) % MOD
        sign ^= 1
    P += (1 - sign * 2) * (k[0] - k[v[0]]) % MOD
    Q += (1 - sign * 2) * range_sum(k[v[0]], k[0]) % MOD
    return (P % MOD, Q % MOD)

# calc sumP, sumQ
sumP = 0
sumQ = 0
for i in range(M):
    tmp = f(X[i])
    P = (tmp[0] + k[0]) * inv2 % MOD
    Q = (tmp[1] + range_sum(0, k[0])) * inv2 % MOD
    sumP = (sumP + P) % MOD
    Q = (Q * M + P * i) % MOD
    sumQ = (sumQ + Q) % MOD

# output
print((sumQ - range_sum(0, sumP)) % MOD)