この解説では基本的に 0 index で話を進めます。

\(0,1\) からなる数列 \(Y=(Y_{0},Y_{1},\dots ,Y_{|Y|-1})\) の転倒数について、以下が成り立ちます。

• \(Y_{i}=0\) が成り立つ \(i\) の数が \(P\) 個で、そのような \(i\) の総和が \(Q\) であるとき、\(Y\) の転倒数は \(Q-\frac{P(P-1)}{2}\)

よって、\(B\) に含まれる \(0\) の数と index の和が分かれば良いです。

ここで、数列の列 \(C=(C_{0},C_{1},\dots C_{M-1})\) を以下のように定義します。

• \(C_{i}=(C_{i,0},C_{i,1},\dots,C_{i,K-1})\) は長さ \(K\) の数列で、\(j\) 番目の要素 \(C_{i,j}\) は \(\operatorname{popcount}(j\operatorname{AND}A_{i})\) に等しい。

\(C_{i}\) に含まれる \(0\) の数を \(P_{i}\) とし、\(0\) である index の和を \(Q_{i}\) としたとき、\(B\) の転倒数は以下のようになります。

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

よって、\(0\) 以上 \(M\) 未満の整数 \(i\) について、\(P_{i}\) と \(Q_{i}\) が分かれば答えがもとまります。

\(P_{i},Q_{i}\) を求めます。これは \(C_{i}\) に含まれる \(0\) の数と \(1\) の数の差と、\(0\) である index の和と \(1\) である index の和の差が求まれば良いです。

ここで、\(K\) を \(A\) の入力と同じように、\(K=\sum 2^{Z_{j}}\) かつ \(0\leq Z_{0}<Z_{1}<\cdots Z_{L - 1}=N-1\) を満たす整数列 \(Z\) を求めます。

そして、その \(Z\) を用いて区間 \([0,K)\) を \([0, 2^{Z_{L-1}}),[2^{Z_{L-1}},2^{Z_{L-2}} + 2^{Z_{L-1}}),\dots,[K - 2^{Z_{0}},K)\) のように分解して、それぞれについて、\(P_{i},Q_{i}\) に対する寄与を考えます。

\(C_{i}\) の連続部分列 \((C_{i,K-2^{Z_{0}}}, C_{i,K-2^{Z_{0}+1}},\dots ,C_{i,K-1})\) の \(0\) の数と \(1\) の数について以下が成り立ちます。

• \((A_{i}\operatorname{AND}(2^{Z_{0}}-1)) \neq 0\) のときは、差が \(0\)
• \((A_{i}\operatorname{AND}(2^{Z_{0}}-1)) = 0\) のときは、全ての要素が \(\operatorname{popcount}(A_{i}\operatorname{AND}(K-2 ^{Z_{0}}))\) に等しい

\(0\) である index の和と \(1\) である index の和について、以下が成り立ちます。

• \(\operatorname{popcount}(A_{i}\operatorname{AND}(2^{Z_{0}}-1)) \geq 2\) のときは、差が \(0\)
• \(\operatorname{popcount}(A_{i}\operatorname{AND}(2^{Z_{0}}-1)) = 1\) のときは、\(\operatorname{popcount}(A_{i}\operatorname{AND}(K-2^{Z_{0}}))\) を \(2\) で割ったあまりである index の和の方が \(2^{Z_{0}-1}\times (A_{i}\operatorname{AND}(2^{Z_{0}}-1))\) だけ小さい
• \(\operatorname{popcount}(A_{i}\operatorname{AND}(2^{Z_{0}}-1)) = 0\) のときは、全ての要素が \(0\) か \(1\)

以上で区間 \([K-2^{Z_{0}},K)\) の \(P_{i},Q_{i}\) に対する寄与が求まりました。他の区間についても同様に求めることができます。

この寄与の計算を全ての \(Z\) について \(1\) つずつ計算するのではなく、適切に区間を分け、累積和などの前計算を行うと、\(P_{i},Q_{i}\) は \(O(L_{i})\) で求めることができます。

具体的には、\(2\leq L_{i}\) であるならば、\([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)\) の \(5\) つの区間に分割します。ここで、\(R_{a}\) は\(K\) から \(K\) を \(2^{a}\) で割ったあまりを引いたものとします。

全ての \(P,Q\) が適切な前計算のもとで \(O(\sum L)\) で求めることができることから、この問題の答えも入力に対して線形の時間で求めることができます。

c++ による実装例

python による実装例

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)