概要

\(N\) 種類の原材料のうちどれがアレルギー原因物質かを決める組み合わせのうち、\(M\) 人のモニターの検査結果と矛盾しないものの個数を求める問題です。\(M \leq 20\) という制約を活かし、包除原理とビットマスクを使って効率的に解きます。

考察

重要な気づき

1. \(R_j = 0\) のモニターによる強い制約

\(R_j = 0\)（反応なし）のモニター \(j\) に割り当てられた原材料は すべて安全 でなければなりません。これにより多くの原材料が「安全確定」となります。

2. \(R_j = 1\) のモニターの「被覆」条件

\(R_j = 1\) のモニターについては、その集合内に 少なくとも1つ アレルギー原因物質が含まれる必要があります。これは集合被覆に類似した条件です。

3. \(M \leq 20\) の活用

\(N\) が大きいため \(2^N\) 通りの全探索は不可能ですが、\(M \leq 20\) なので「モニターの部分集合」に対する包除原理（\(2^M\) 通り）が使えます。

素朴なアプローチの問題点

各原材料を「アレルゲンか安全か」で全探索すると \(2^N\) 通り（\(N\) は最大 \(2 \times 10^5\)）で不可能です。

解決の鍵

各原材料を「どの \(R=1\) モニターに使われているか」のビットマスクでグループ分けします。同じマスクの原材料は全て対称なので、グループごとにまとめて計算できます。

アルゴリズム

ステップ1: 原材料の分類

各原材料 \(i\) について、それを使用するモニターのビットマスク \(\text{material\_mask}[i]\) を求めます。

• \(\text{material\_mask}[i]\) と「\(R=0\) モニター集合」が交差する → 安全確定（アレルゲンにできない）
• どのモニターにも含まれない → 自由（アレルゲンでも安全でもよく、結果に影響しない）
• それ以外 → \(R=1\) モニターのみに出現し、アレルゲンにできる候補

ステップ2: マスクによるグループ化

候補の原材料を「\(R=1\) モニターに対するビットマスク」でグループ化し、各マスクの個数 \(\text{mask\_count}[\text{msk}]\) を求めます。

ステップ3: 包除原理

\(P\) 個の \(R=1\) モニター全てを「被覆」する（各モニターの集合に少なくとも1つアレルゲンが存在する）割り当ての数を包除原理で求めます：

\[\text{Answer} = \sum_{T \subseteq \text{positive monitors}} (-1)^{|T|} \cdot 2^{c(T) + \text{free}}\]

ここで \(c(T)\) は「マスクが \(T\) と交差しない原材料の個数」（= \(T\) に含まれるどのモニターにも使われていない候補原材料の数）です。これらの原材料はアレルゲンにしても \(T\) 内のモニターに影響しないため、自由に選べます。

ステップ4: 部分和変換（SOS）で高速化

\(c(T)\) の計算を高速化するため、\(f[\text{mask}] = \sum_{s \subseteq \text{mask}} \text{mask\_count}[s]\) を部分和変換（Sum over Subsets）で前計算します。すると：

\[c(T) = f[\overline{T}] \quad (\overline{T} \text{は } T \text{の補集合})\]

計算量

• 時間計算量: \(O(P \cdot 2^P + N + \sum k_j)\)（\(P\) は \(R=1\) のモニター数、\(P \leq M \leq 20\)）
• 空間計算量: \(O(2^P + N)\)

実装のポイント

• ビットのリマップ: \(R=1\) のモニターだけを \(0, 1, \ldots, P-1\) に詰め直すことで、\(2^M\) ではなく \(2^P\) のループで済みます（\(R=0\) のモニターは事前に処理済みのため不要）。

• 2のべき乗の前計算: pow(2, cnt, MOD) を毎回計算する代わりにテーブルを用意します。

• \(\text{mask\_count}[0]\) の扱い: どのモニターにも含まれない原材料（material_mask に登録されない）は free_count として別途管理します。これらは被覆条件に一切影響しないので、常に \(2^{\text{free\_count}}\) を掛ける効果があります。

  ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    MOD = 998244353
    
    # For each material, compute bitmask of which monitors use it
    # material_mask[i] = bitmask of monitors that include material i
    material_mask = defaultdict(int)
    
    sets = []
    for j in range(M):
        k = int(input_data[idx]); idx += 1
        s = []
        for _ in range(k):
            v = int(input_data[idx]); idx += 1
            s.append(v)
            material_mask[v] |= (1 << j)
        sets.append(s)
    
    R = []
    for j in range(M):
        R.append(int(input_data[idx])); idx += 1
    
    # R as bitmask: positive_mask = set of monitors with R=1
    positive_mask = 0
    for j in range(M):
        if R[j] == 1:
            positive_mask |= (1 << j)
    
    # For R_j = 0 monitors: all materials in S_j must be safe (not allergen)
    # So any material that appears in a monitor with R=0 must be safe.
    # Let forced_safe = set of materials that must be safe
    zero_mask = 0
    for j in range(M):
        if R[j] == 0:
            zero_mask |= (1 << j)
    
    # Materials that appear in any R=0 monitor must be safe.
    # So we only consider materials that do NOT appear in any R=0 monitor as potentially allergen.
    
    # Group materials by their mask (restricted to positive monitors only)
    # A material can be allergen only if material_mask[i] & zero_mask == 0
    # (i.e., it doesn't appear in any R=0 monitor)
    
    # Count materials by their "positive monitor mask"
    # Also count "free" materials: those not in any monitor at all (mask=0 among positive monitors)
    # and materials that appear only in R=0 monitors (forced safe, can't be allergen)
    
    # mask_count[mask] = number of materials with that positive-monitor-mask that are eligible (not in any R=0 monitor)
    mask_count = defaultdict(int)
    
    # Materials not mentioned in any monitor
    mentioned = set(material_mask.keys())
    free_count = N - len(mentioned)  # these have mask=0, not in any monitor, can be allergen or safe freely
    
    for mat, msk in material_mask.items():
        if msk & zero_mask:
            # This material appears in some R=0 monitor, must be safe
            continue
        # Only keep bits for positive monitors (well, it can't have R=0 bits since we checked)
        mask_count[msk] += 1
    
    # free materials (not in any monitor): they can be allergen or safe, each contributes factor 2
    # They have mask = 0 among all monitors, and don't appear in any R=0 monitor
    # mask_count[0] are materials that appear only in R=1 monitors but... wait, mask 0 means
    # they don't appear in any monitor among positive ones either. But they ARE mentioned in some monitor.
    # Actually if material_mask[i] has only R=0 bits, then msk & zero_mask != 0, so they're excluded.
    # If material_mask[i] = 0, that can't happen since we only add to material_mask when mentioned.
    
    # So free_count materials contribute 2^free_count factor, and mask_count[0] materials also contribute 2^mask_count[0]
    # because choosing them as allergen doesn't cover any positive monitor.
    
    # Now we need: for the positive monitors (positive_mask), every such monitor must be "hit" by at least one allergen.
    # This is a set cover / inclusion-exclusion on 2^M subsets.
    
    # Inclusion-exclusion: number of assignments covering all positive monitors =
    # sum over T subset of positive monitors: (-1)^|T| * product over each mask-group of (ways that group doesn't hit any monitor in T)
    
    # For a subset T of positive_mask: a material with positive-monitor-mask `msk` can be allergen only if msk & T == 0
    # (otherwise it would hit a monitor in T, but we're counting assignments that MISS all of T)
    # Wait, inclusion-exclusion for "all covered":
    # = sum_{T ⊆ positive_mask} (-1)^{|T|} * (number of assignments where no allergen hits any monitor in T)
    
    # For subset T: count of eligible materials with msk & T == 0 => each can be 0 or 1 (safe or allergen), others must be safe
    # So contribution = 2^(count of materials with msk & T == 0) [including free and mask_count[0]]
    
    # Precompute for each T ⊆ positive_mask: sum of mask_count[msk] for msk & T == 0
    # This is a "subset sum over superset" / zeta transform.
    
    num_positive = bin(positive_mask).count('1')
    
    # Remap positive monitors to consecutive bits for efficiency
    pos_monitors = []
    for j in range(M):
        if R[j] == 1:
            pos_monitors.append(j)
    P = len(pos_monitors)
    
    # Remap masks
    remap_mask_count = [0] * (1 << P)
    for msk, cnt in mask_count.items():
        new_msk = 0
        for pi, j in enumerate(pos_monitors):
            if msk & (1 << j):
                new_msk |= (1 << pi)
        remap_mask_count[new_msk] += cnt
    
    base_free = free_count + mask_count.get(0, 0)  # mask=0 doesn't exist in mask_count for mentioned ones unless... 
    # Actually let me reconsider. A material mentioned only in positive monitors could have msk with only positive bits.
    # msk=0 in mask_count means it appears in some monitors but none of them are positive and it's not in any R=0 monitor.
    # That's impossible: if it's mentioned, material_mask[i] != 0, and if msk & zero_mask == 0, then it has bits only in 
    # positive monitors. But if none of those bits are set... that means it appears only in monitors that are neither R=0 nor R=1?
    # No, every monitor is either R=0 or R=1. So if msk & zero_mask == 0, all bits of msk are in positive monitors.
    # msk=0 would mean material_mask[i]=0, but we said material_mask only has mentioned materials. Contradiction.
    # So mask_count[0] = 0 always. Good.
    
    # For subset T (in remapped bits): count of materials with new_msk & T == 0
    # = sum of remap_mask_count[s] for s subset of complement(T)
    # This is the "sum over subsets of complement" = superset zeta of remap_mask_count evaluated at T's complement
    # Or equivalently, subset sum (SOS) where f[T] = sum_{S ⊆ T} remap_mask_count[S], then we want f[complement(T)]
    # i.e., f[(1<<P)-1 ^ T]
    
    # Compute SOS (subset sum): f[mask] = sum of remap_mask_count[s] for s ⊆ mask
    f = remap_mask_count[:]
    for i in range(P):
        for mask in range(1 << P):
            if mask & (1 << i):
                f[mask] += f[mask ^ (1 << i)]
    
    full = (1 << P) - 1
    
    # Precompute powers of 2 mod MOD
    max_pow = N + 1
    pow2 = [1] * (max_pow + 1)
    for i in range(1, max_pow + 1):
        pow2[i] = pow2[i - 1] * 2 % MOD
    
    # popcount
    ans = 0
    for T in range(1 << P):
        cnt = f[full ^ T] + free_count  # materials that can be freely chosen (allergen or safe)
        # Each of these cnt materials: 2 choices. Others must be safe.
        sign = 1 if bin(T).count('1') % 2 == 0 else -1
        ans = (ans + sign * pow2[cnt]) % MOD
    
    print(ans % MOD)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。