Overview

This problem asks us to find the number of combinations that determine which of \(N\) types of raw materials are allergens, such that they do not contradict the test results of \(M\) monitors. We leverage the constraint \(M \leq 20\) and solve efficiently using the inclusion-exclusion principle and bitmasks.

Analysis

Key Observations

1. Strong constraints from monitors with \(R_j = 0\)

For monitor \(j\) with \(R_j = 0\) (no reaction), all raw materials assigned to that monitor must be safe. This causes many raw materials to become “confirmed safe.”

2. The “coverage” condition for monitors with \(R_j = 1\)

For monitors with \(R_j = 1\), their set must contain at least one allergen. This is a condition similar to set cover.

3. Leveraging \(M \leq 20\)

Since \(N\) is large, exhaustive search over \(2^N\) possibilities is impossible. However, since \(M \leq 20\), we can use the inclusion-exclusion principle over “subsets of monitors” (\(2^M\) possibilities).

Issues with the Naive Approach

Exhaustively searching all possibilities of each raw material being “allergen or safe” requires \(2^N\) cases (\(N\) can be up to \(2 \times 10^5\)), which is infeasible.

Key to the Solution

We group each raw material by its bitmask representing “which \(R=1\) monitors use it.” Raw materials with the same mask are all symmetric, so we can compute them together as a group.

Algorithm

Step 1: Classification of Raw Materials

For each raw material \(i\), compute \(\text{material\_mask}[i]\), the bitmask of monitors that use it.

• If \(\text{material\_mask}[i]\) intersects with the “\(R=0\) monitor set” → confirmed safe (cannot be an allergen)
• If not included in any monitor → free (can be either allergen or safe, does not affect the result)
• Otherwise → appears only in \(R=1\) monitors and is a candidate that can be an allergen

Step 2: Grouping by Mask

Group candidate raw materials by their “bitmask with respect to \(R=1\) monitors” and compute the count \(\text{mask\_count}[\text{msk}]\) for each mask.

Step 3: Inclusion-Exclusion Principle

Use the inclusion-exclusion principle to find the number of assignments that “cover” all \(P\) monitors with \(R=1\) (i.e., at least one allergen exists in each monitor’s set):

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

Here, \(c(T)\) is “the number of raw materials whose mask does not intersect with \(T\)” (= the number of candidate raw materials not used by any monitor in \(T\)). These raw materials do not affect any monitor in \(T\) even if made allergens, so they can be chosen freely.

Step 4: Speed Up with Sum over Subsets (SOS)

To efficiently compute \(c(T)\), we precompute \(f[\text{mask}] = \sum_{s \subseteq \text{mask}} \text{mask\_count}[s]\) using the Sum over Subsets (SOS) transform. Then:

\[c(T) = f[\overline{T}] \quad (\overline{T} \text{ is the complement of } T)\]

Complexity

• Time complexity: \(O(P \cdot 2^P + N + \sum k_j)\) (where \(P\) is the number of monitors with \(R=1\), \(P \leq M \leq 20\))
• Space complexity: \(O(2^P + N)\)

Implementation Notes

• Bit remapping: By repacking only the \(R=1\) monitors to indices \(0, 1, \ldots, P-1\), we only need a loop of size \(2^P\) instead of \(2^M\) (since \(R=0\) monitors have already been processed and are no longer needed).

• Precomputation of powers of 2: Instead of computing pow(2, cnt, MOD) each time, prepare a lookup table.

• Handling \(\text{mask\_count}[0]\): Raw materials not included in any monitor (not registered in material_mask) are managed separately as free_count. Since they have no effect on the coverage condition whatsoever, they always contribute a factor of \(2^{\text{free\_count}}\).

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.