概要

「反応なし(0)のモニターが食べた原材料はすべて安全」「反応あり(1)の各モニターには少なくとも1つ原因物質が含まれる」を同時に満たす、原因物質（アレルゲン）集合の個数を \(998244353\) で数えます。
\(M \le 20\) を利用して、包除原理と高速ゼータ変換（subset sum DP）で一気に数え上げます。

考察

重要な観察1：\(R_j=0\) のモニターに含まれる原材料は「強制的に安全」

モニター \(j\) が反応なし（\(R_j=0\)）なら、集合 \(S_j\) の中にアレルゲンは 1つも存在してはいけません。
したがって、ある原材料が どれか1人でも \(R=0\) のモニターに含まれていれば、その原材料は必ず安全です（選択肢から除外してよい）。

コードでは、各原材料 \(i\) について「どのモニター集合に入っているか」をビットマスク ing_mask[i] で持ち、
ing_mask[i] & negMask != 0（negMask は \(R=0\) のモニター集合）なら、その原材料は捨てます（強制安全）。

重要な観察2：残った原材料は「どの“反応ありモニター”を満たし得るか」だけが重要

\(R=1\) のモニター（以下「正のモニター」）は、各々「自分の集合 \(S_j\) の中にアレルゲンが1つ以上必要」です。
そこで正のモニターだけを取り出し（個数 \(p \le 20\)）、各原材料を

• 「正のモニターのうち、どれに含まれているか」

という \(p\) ビットのマスクに圧縮します（コードの reduced）。

同じ reduced を持つ原材料は、この条件に対して完全に同等なので、個数だけ数えれば十分です（freq[mask]）。

素朴案が無理な理由

• 原材料は最大 \(N=2\times 10^5\) なので、全探索 \(2^N\) は不可能。
• しかしモニターは最大 \(20\) 人なので、モニター側（条件側）を \(2^M\) 程度で回す方針にすれば間に合います。

解決策：包除原理で「全員満たす」を数える

正のモニター全員が満たされる（各人に少なくとも1つアレルゲンが入る）条件は、 「満たされない人が存在しない」の否定を使って包除原理で数えられます。

アルゴリズム

正のモニター数を \(p\)、その全集合を \(U=\{0,1,\dots,p-1\}\) とします。

1. 強制安全の除去とマスク圧縮

1. \(R_j=0\) のモニター集合を negMask とする。
2. 各原材料 \(i\) について、登場するモニター集合を ing_mask[i] に作る。
3. ing_mask[i] & negMask != 0 なら強制安全なので無視。
4. 残った原材料について、正のモニター部分だけ抜き出して \(p\) ビットに圧縮したマスクを reduced とし、freq[reduced]++。
   • 残った原材料数を \(K\) とする（自由にアレルゲンにできる候補数）。

2. 包除原理の形

正のモニターの部分集合 \(T \subseteq U\) について、 「\(T\) の全員が 満たされない（=その人の集合にアレルゲンが1つも入らない）」状況を数えます。

\(T\) の誰も満たさないためには、選ぶアレルゲン原材料が どのモニター in \(T\) にも含まれていない必要があります。
つまり、アレルゲンに選べるのは

• マスク mask が \(mask \cap T = \emptyset\) を満たす原材料

だけです。

その個数を \(g(T)\) とすると、「\(T\) を全員満たさない」アレルゲン集合の数は [ 2^{g(T)} ] （その \(g(T)\) 個から好きに選ぶだけ）です。

よって包除原理で答えは [ \text{ans} = \sum_{T \subseteq U} (-1)^{|T|}\, 2^{g(T)} ]

3. \(g(T)\) を全 \(T\) について高速に求める（ゼータ変換）

freq[mask] があるとき、 [ g(T) = \sum{\substack{mask \subseteq U \ mask \cap T=\emptyset}} freq[mask] = \sum{mask \subseteq (U \setminus T)} freq[mask] ] となります。

ここで [ F[X] = \sum_{sub \subseteq X} freq[sub] ] を全 \(X\) について計算できれば、 [ g(T) = F[U \setminus T] ] が一発で取れます。

この \(F\) は「高速ゼータ変換（subset sum DP）」で \(O(p2^p)\) で計算できます（コードの in-place 変換部分）。

最後に各 \(T\) について g = F[allmask ^ T] として \((-1)^{|T|} 2^g\) を足し引きします。

計算量

• 時間計算量:
  
  • 入力処理・マスク構築: \(O\!\left(\sum k_j\right)\)
    
  • マスク圧縮（各原材料の set bit を舐める）: 最大でも \(O(NM)\) 程度だが \(M \le 20\) なので十分軽い
    
  • ゼータ変換: \(O(p2^p)\)（\(p \le 20\) なので最大約 \(2{,}0\times 10^7\) 操作）
    
  • 包除原理の総和: \(O(2^p)\)
    よって全体として \(O\!\left(\sum k_j + p2^p\right)\) 。
• 空間計算量: \(O(N + 2^p)\)

実装のポイント

• 「反応なし(0)に出た原材料は全部安全」を最初に適用すると、以降は正のモニターだけ見ればよくなり、問題が一気に小さくなります。

• freq をそのままゼータ変換で上書きして F として使う（in-place）ことでメモリを節約できます。

• \(2^{g(T)}\) を何度も使うので、\(K\) までの pow2[i]=2^i mod MOD を前計算します。

• \(p=0\)（反応ありが1人もいない）でも式は自然に動き、答えは \(2^K\)（自由な原材料を好きにアレルゲン化できる）になります。

  ソースコード

import sys

MOD = 998244353

data = sys.stdin.buffer.read()
n_data = len(data)
ptr = 0

def next_int():
    global ptr
    while ptr < n_data and data[ptr] <= 32:
        ptr += 1
    v = 0
    while ptr < n_data and data[ptr] > 32:
        v = v * 10 + (data[ptr] - 48)
        ptr += 1
    return v

N = next_int()
M = next_int()

ing_mask = [0] * N
for j in range(M):
    k = next_int()
    bit = 1 << j
    for _ in range(k):
        x = next_int() - 1
        ing_mask[x] |= bit

R = [next_int() for _ in range(M)]

negMask = 0
pos_indices = []
for j, r in enumerate(R):
    if r == 0:
        negMask |= 1 << j
    else:
        pos_indices.append(j)

p = len(pos_indices)
posMask = 0
posToIdx = [-1] * M
for idx, j in enumerate(pos_indices):
    posMask |= 1 << j
    posToIdx[j] = idx

L = 1 << p
freq = [0] * L
K = 0

for om in ing_mask:
    if om & negMask:
        continue
    m = om & posMask
    reduced = 0
    while m:
        b = m & -m
        j = b.bit_length() - 1
        reduced |= 1 << posToIdx[j]
        m -= b
    freq[reduced] += 1
    K += 1

pow2 = [1] * (K + 1)
for i in range(1, K + 1):
    pow2[i] = (pow2[i - 1] * 2) % MOD

f = freq  # in-place zeta transform: f[U] = sum_{sub ⊆ U} freq[sub]
for i in range(p):
    step = 1 << i
    jump = step << 1
    for base in range(0, L, jump):
        start = base + step
        end = base + jump
        for m in range(start, end):
            f[m] += f[m - step]

allmask = L - 1
ans = 0
for T in range(L):
    g = f[allmask ^ T]  # count of items with (mask & T) == 0
    term = pow2[g]
    if T.bit_count() & 1:
        ans -= term
        if ans < 0:
            ans += MOD
    else:
        ans += term
        if ans >= MOD:
            ans -= MOD

print(ans)

---

この解説は gpt-5.2-high によって生成されました。