Overview

This is a problem of identifying allergens from \(N\) types of raw ingredients. Given the test results (presence or absence of allergic reactions) of \(M\) monitors, we need to find the number of allergen combinations (among \(2^N\) possibilities that satisfy the conditions) that are consistent with all results, modulo \(998244353\).

Analysis

1. Information from monitors with no reaction (\(R_j = 0\))

For a monitor \(j\) who did not have an allergic reaction (\(R_j = 0\)), all raw ingredients \(S_j\) they consumed are confirmed to be safe (not allergens). Therefore, we first mark all raw ingredients consumed by monitors with \(R_j = 0\) as “confirmed safe” and exclude them from allergen candidates.

2. Information from monitors with reactions (\(R_j = 1\)) and inclusion-exclusion principle

Let \(M'\) be the number of monitors with \(R_j = 1\) (by the constraints, \(M' \leq M \leq 20\)). For the remaining “not confirmed safe” ingredients, we need to assign allergens (at least one) satisfying the following condition: - Condition: For every monitor with \(R_j = 1\), at least one allergen is included among the ingredients they consumed.

Directly counting cases where “all monitors consume at least one allergen” is difficult. Therefore, we apply the inclusion-exclusion principle.

Let the set of monitors with \(R_j = 1\) be \(\{1, 2, \ldots, M'\}\). When we choose a subset \(S\) of monitors, we consider the situation where “only the monitors in \(S\) might not consume any allergen (= might not react)”. This can be rephrased as “all ingredients consumed by monitors not in \(S\) (i.e., \(\overline{S}\)) are safe”.

For each not-confirmed-safe ingredient \(i\), we represent the set of \(R_j = 1\) monitors who consume it as a bitmask \(mask_i\). The condition for ingredient \(i\) not to be consumed by any monitor in \(\overline{S}\) is \(mask_i \subseteq S\).

Therefore, when only monitors in \(S\) might not react, the ingredients that can be freely chosen (either safe or allergen) are only those satisfying \(mask_i \subseteq S\). If we denote this count as \(F(S)\), there are \(2^{F(S)}\) ways to choose such ingredients.

By the inclusion-exclusion principle, the number of combinations where all monitors react (= no monitor is in a “no reaction” situation) is given by: $\( \sum_{S \subseteq \{1, \dots, M'\}} (-1)^{M' - |S|} 2^{F(S)} \)$

3. Speedup using fast zeta transform

If we naively compute \(F(S)\) for all \(S\), we need to scan \(N\) ingredients for each \(S\), taking \(O(N \cdot 2^{M'})\) time, which would result in TLE (Time Limit Exceeded).

Here, for each mask \(T\), let \(count[T]\) be the number of ingredients with \(mask_i = T\). The desired \(F(S)\) can be expressed as: $\( F(S) = \sum_{T \subseteq S} count[T] \)$

This is exactly the form of sum over subsets (SOS DP / fast zeta transform). Using the fast zeta transform, we can efficiently compute \(F(S)\) for all \(S\) in \(O(M' \cdot 2^{M'})\).

Algorithm

1. Identify safe ingredients: Mark all ingredients contained in \(S_j\) of monitors \(j\) with \(R_j = 0\) as “confirmed safe”.
2. Extract monitors with reactions: Extract only monitors with \(R_j = 1\) and assign new indices from \(0\) to \(M'-1\).
3. Compute masks: For each ingredient \(i\), if it is not confirmed safe, compute the bitmask \(mask_i\) representing the set of \(R_j=1\) monitors who consume it.
4. Create frequency array: Prepare an array count of length \(2^{M'}\) and record the occurrence count of each ingredient’s \(mask_i\).
5. Fast zeta transform (SOS DP): Apply the fast zeta transform to the count array to obtain the total number of ingredients \(F(S)\) satisfying \(mask_i \subseteq S\) for each \(S\).
6. Inclusion-exclusion summation: For all \(S\) (integers from \(0\) to \(2^{M'}-1\)), add or subtract \(2^{F(S)}\) according to the parity of \(M' - |S|\), and compute the answer modulo \(998244353\).

Complexity

• Time complexity: \(O(N + \sum k_j + M \cdot 2^M)\)

  • Identifying safe ingredients and computing masks takes \(O(N + \sum k_j)\).
  • The fast zeta transform takes \(O(M' \cdot 2^{M'})\), and the inclusion-exclusion summation takes \(O(2^{M'})\). Since \(M' \leq M \leq 20\), this results in at most \(20 \times 2^{20} \approx 2 \times 10^7\) operations, which is well within the time limit.

• Space complexity: \(O(N + 2^M)\)

  • \(O(N)\) for the array holding ingredient information, and \(O(2^{M'})\) for the fast zeta transform table.

Implementation Notes

• Precomputation of powers of \(2\): Since we compute \(2^{F(S)} \bmod 998244353\) many times in the inclusion-exclusion calculation, precomputing a table of \(2^x \bmod 998244353\) values speeds up the overall constant factor.

• Handling sets with bit operations: By representing sets of monitors as bit strings (integers), we can efficiently compute set inclusion relations and element counts (popcount).

  Source Code

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()

---

This editorial was generated by gemini-3.5-flash-thinking.