Overview

We count the number of allergen (causative substance) sets modulo \(998244353\) that simultaneously satisfy “all ingredients eaten by monitors with no reaction (0) are safe” and “each monitor with a reaction (1) contains at least one causative substance.”
Using the constraint \(M \le 20\), we perform the counting all at once with inclusion-exclusion principle and fast zeta transform (subset sum DP).

Analysis

Key Observation 1: Ingredients contained in monitors with \(R_j=0\) are “forced to be safe”

If monitor \(j\) has no reaction (\(R_j=0\)), then not a single allergen can exist in the set \(S_j\).
Therefore, if an ingredient is contained in even one monitor with \(R=0\), that ingredient must be safe (it can be excluded from consideration).

In the code, for each ingredient \(i\), we store “which monitors’ sets it belongs to” as a bitmask ing_mask[i].
If ing_mask[i] & negMask != 0 (where negMask is the set of monitors with \(R=0\)), then that ingredient is discarded (forced safe).

Key Observation 2: For remaining ingredients, only “which reaction-positive monitors they can satisfy” matters

Monitors with \(R=1\) (hereafter “positive monitors”) each require “at least one allergen in their set \(S_j\).”
So we extract only the positive monitors (count \(p \le 20\)), and compress each ingredient into

• a \(p\)-bit mask representing “which positive monitors contain it”

(this is reduced in the code).

Ingredients with the same reduced value are completely equivalent with respect to this condition, so it suffices to just count them (freq[mask]).

Why a naive approach doesn’t work

• There can be up to \(N=2\times 10^5\) ingredients, so exhaustive search over \(2^N\) is impossible.
• However, there are at most \(20\) monitors, so an approach that iterates over the monitor side (condition side) in \(2^M\) time is feasible.

Solution: Count “all satisfied” using inclusion-exclusion

The condition that all positive monitors are satisfied (each person has at least one allergen) can be counted using inclusion-exclusion on the negation “there exists someone who is not satisfied.”

Algorithm

Let the number of positive monitors be \(p\), and the full set be \(U=\{0,1,\dots,p-1\}\).

1. Removal of forced-safe ingredients and mask compression

1. Let negMask be the set of monitors with \(R_j=0\).
2. For each ingredient \(i\), construct ing_mask[i] representing the set of monitors it appears in.
3. If ing_mask[i] & negMask != 0, the ingredient is forced safe, so ignore it.
4. For remaining ingredients, extract only the positive monitor bits and compress into a \(p\)-bit mask called reduced, then increment freq[reduced]++.
   • Let \(K\) be the number of remaining ingredients (candidates that can freely be made into allergens).

2. Form of the inclusion-exclusion

For a subset \(T \subseteq U\) of positive monitors, we count the situations where “all members of \(T\) are not satisfied (= no allergen is in their set).”

For none of the monitors in \(T\) to be satisfied, the allergen ingredients we choose must not be contained in any monitor in \(T\).
In other words, only ingredients whose mask satisfies \(mask \cap T = \emptyset\) can be chosen as allergens.

Let \(g(T)\) be the count of such ingredients. Then the number of allergen sets where “all of \(T\) are unsatisfied” is $\( 2^{g(T)} \)\( (we simply choose freely from those \)g(T)$ ingredients).

Therefore, by inclusion-exclusion, the answer is $\( \text{ans} = \sum_{T \subseteq U} (-1)^{|T|}\, 2^{g(T)} \)$

3. Computing \(g(T)\) for all \(T\) efficiently (zeta transform)

Given freq[mask], $\( g(T) = \sum_{\substack{mask \subseteq U \\ mask \cap T=\emptyset}} freq[mask] = \sum_{mask \subseteq (U \setminus T)} freq[mask] \)$

If we can compute $\( F[X] = \sum_{sub \subseteq X} freq[sub] \)\( for all \)X\(, then \)\( g(T) = F[U \setminus T] \)$ can be obtained immediately.

This \(F\) can be computed in \(O(p2^p)\) using “fast zeta transform (subset sum DP)” (the in-place transformation part of the code).

Finally, for each \(T\), we set g = F[allmask ^ T] and add/subtract \((-1)^{|T|} 2^g\).

Complexity

• Time complexity:
  
  • Input processing and mask construction: \(O\!\left(\sum k_j\right)\)
    
  • Mask compression (iterating over set bits of each ingredient): at most \(O(NM)\), but sufficiently fast since \(M \le 20\)
    
  • Zeta transform: \(O(p2^p)\) (at most about \(2.0\times 10^7\) operations since \(p \le 20\))
    
  • Inclusion-exclusion summation: \(O(2^p)\)
    Overall: \(O\!\left(\sum k_j + p2^p\right)\).
• Space complexity: \(O(N + 2^p)\)

Implementation Notes

• Applying “all ingredients that appeared in reaction-0 monitors are safe” first means we only need to look at positive monitors afterwards, drastically reducing the problem size.

• Overwriting freq in-place with the zeta transform to use as F saves memory.

• Since \(2^{g(T)}\) is used many times, we precompute pow2[i]=2^i mod MOD up to \(K\).

• Even when \(p=0\) (no monitors with a reaction), the formula works naturally, and the answer becomes \(2^K\) (free ingredients can be freely made into allergens).

  Source Code

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)

---

This editorial was generated by gpt-5.2-high.