概要

\(N\) 種類の原材料からアレルギー原因物質を特定する問題です。\(M\) 人のモニターの検査結果（アレルギー反応の有無）が与えられたとき、それらすべての結果と矛盾しないアレルギー原因物質の組み合わせ（\(2^N\) 通りのうち条件を満たすもの）の個数を \(\bmod 998244353\) で求めます。

考察

1. 反応なし（\(R_j = 0\)）のモニターからの情報

アレルギー反応が出なかったモニター \(j\)（\(R_j = 0\)）が摂取した原材料 \(S_j\) は、すべて安全（アレルギー原因物質ではない）であることが確定します。 したがって、まず \(R_j = 0\) であるすべてのモニターが摂取した原材料を「安全確定」としてマークし、アレルギー原因物質の候補から除外します。

2. 反応あり（\(R_j = 1\)）のモニターからの情報と包除原理

\(R_j = 1\) であるモニターの数を \(M'\) とします（制約より \(M' \leq M \leq 20\)）。 残った「安全が確定していない原材料」について、以下の条件を満たすようにアレルギー原因物質（1つ以上）を割り当てる必要があります。 - 条件： \(R_j = 1\) であるすべてのモニターについて、自身が摂取した原材料の中に少なくとも1つアレルギー原因物質が含まれる。

「すべてのモニターが少なくとも1つのアレルギー物質を摂取する」という条件を直接数え上げるのは困難です。そこで、包除原理を適用します。

\(R_j = 1\) であるモニターの集合を \(\{1, 2, \ldots, M'\}\) とします。 あるモニターの「補集合」 \(S\) を選んだとき、「\(S\) に含まれるモニターだけが、アレルギー原因物質を1つも摂取しない（＝反応しない）可能性がある」という状況を考えます。 これは、「\(S\) に含まれないモニター（すなわち \(\overline{S}\)）に摂取される原材料は、すべて安全である」と言い換えることができます。

安全が確定していない原材料 \(i\) について、それを摂取する \(R_j = 1\) のモニターの集合をビットマスク \(mask_i\) で表します。 原材料 \(i\) が \(\overline{S}\) のモニターに摂取されないための条件は、 \(mask_i \subseteq S\) となることです。

したがって、\(S\) に含まれるモニターだけが反応しない可能性があるとき、アレルギー原因物質として自由に選べる（安全でもアレルギー物質でもよい）原材料は、 \(mask_i \subseteq S\) を満たす原材料のみです。 この個数を \(F(S)\) とすると、そのような原材料の選び方は \(2^{F(S)}\) 通り存在します。

包除原理により、すべてのモニターが反応する（＝どのモニターも「反応しない」という状況にならない）組み合わせの数は、以下の式で求まります。 $\( \sum_{S \subseteq \{1, \dots, M'\}} (-1)^{M' - |S|} 2^{F(S)} \)$

3. 高速ゼータ変換による高速化

すべての \(S\) について \(F(S)\) を愚直に求めると、各 \(S\) について \(N\) 個の原材料を走査するため \(O(N \cdot 2^{M'})\) の時間がかかり、TLE（実行時間制限超過）になってしまいます。

ここで、各マスク \(T\) について、 \(mask_i = T\) となる原材料の個数を \(count[T]\) とします。 求めたい \(F(S)\) は以下のように表せます。 $\( F(S) = \sum_{T \subseteq S} count[T] \)$

これはまさに下位集合の総和（SOS DP / 高速ゼータ変換）の形をしています。高速ゼータ変換を用いることで、すべての \(S\) に対する \(F(S)\) を \(O(M' \cdot 2^{M'})\) で効率的に計算することができます。

アルゴリズム

1. 安全な原材料の特定: \(R_j = 0\) であるモニター \(j\) の原材料 \(S_j\) に含まれるすべての原材料を「安全確定」とマークします。
2. 反応ありモニターの抽出: \(R_j = 1\) であるモニターのみを抽出し、新しく \(0\) から \(M'-1\) までのインデックスを割り振ります。
3. マスクの計算: 各原材料 \(i\) について、安全確定でなければ、それを摂取する \(R_j=1\) のモニターの集合を表すビットマスク \(mask_i\) を計算します。
4. 頻度配列の作成: 長さ \(2^{M'}\) の配列 count を用意し、各原材料の \(mask_i\) の出現回数を記録します。
5. 高速ゼータ変換 (SOS DP): count 配列に対して高速ゼータ変換を行い、各 \(S\) について \(mask_i \subseteq S\) となる原材料の総数 \(F(S)\) を求めます。
6. 包除原理の集計: すべての \(S\)（\(0\) から \(2^{M'}-1\) までの整数）について、 \(M' - |S|\) の奇偶に応じて \(2^{F(S)}\) を足し引きし、答えを \(\bmod 998244353\) で求めます。

計算量

• 時間計算量: \(O(N + \sum k_j + M \cdot 2^M)\)

  • 安全な原材料の特定およびマスクの計算に \(O(N + \sum k_j)\) かかります。
  • 高速ゼータ変換に \(O(M' \cdot 2^{M'})\)、包除原理の集計に \(O(2^{M'})\) かかります。\(M' \leq M \leq 20\) であるため、最大でも \(20 \times 2^{20} \approx 2 \times 10^7\) 回の演算となり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N + 2^M)\)

  • 原材料の情報を保持する配列に \(O(N)\)、高速ゼータ変換のためのテーブルに \(O(2^{M'})\) のメモリを使用します。

実装のポイント

• \(2\) の累乗の事前計算: 包除原理の計算で \(2^{F(S)} \bmod 998244353\) を何度も計算するため、あらかじめ \(2^x \bmod 998244353\) の値をテーブルに前計算しておくことで、全体の定数倍を高速化できます。

• ビット演算による集合の扱い: モニターの集合をビット列（整数）として扱うことで、集合の包含関係や要素数（popcount）の計算を高速に行うことができます。

  ソースコード

import sys


def solve():
    # Fast I/O
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    M = int(input_data[1])

    idx = 2
    S = []
    for _ in range(M):
        k = int(input_data[idx])
        s_list = [int(x) for x in input_data[idx + 1 : idx + 1 + k]]
        S.append(s_list)
        idx += 1 + k

    R = [int(x) for x in input_data[idx : idx + M]]

    MOD = 998244353

    # Identify ingredients that must be safe (R_j = 0)
    is_zero_raw = [False] * (N + 1)
    for j in range(M):
        if R[j] == 0:
            for s in S[j]:
                is_zero_raw[s] = True

    # Extract indices of positive response monitors (R_j = 1)
    pos_monitors = []
    for j in range(M):
        if R[j] == 1:
            pos_monitors.append(j)

    M_prime = len(pos_monitors)

    # Calculate masks for each candidate allergen
    masks = [0] * (N + 1)
    for k in range(M_prime):
        j = pos_monitors[k]
        for s in S[j]:
            if not is_zero_raw[s]:
                masks[s] |= 1 << k

    # Count frequency of each mask
    count = [0] * (1 << M_prime)
    for i in range(1, N + 1):
        if not is_zero_raw[i]:
            count[masks[i]] += 1

    # Fast Zeta Transform (SOS DP)
    F = list(count)
    for i in range(M_prime):
        bit = 1 << i
        for mask in range(1 << M_prime):
            if not (mask & bit):
                F[mask | bit] += F[mask]

    # Precompute powers of 2
    pow2 = [1] * (N + 1)
    for i in range(1, N + 1):
        pow2[i] = (pow2[i - 1] * 2) % MOD

    # Precompute popcounts for inclusion-exclusion
    pc = [0] * (1 << M_prime)
    for i in range(1, 1 << M_prime):
        pc[i] = pc[i >> 1] + (i & 1)

    # Inclusion-Exclusion Principle
    ans = 0
    for S_mask in range(1 << M_prime):
        diff = M_prime - pc[S_mask]
        val = pow2[F[S_mask]]
        if diff % 2 == 1:
            ans = (ans - val) % MOD
        else:
            ans = (ans + val) % MOD

    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。