Overview

This problem asks us to determine the total number of combinations for assigning each ingredient as either an “allergen (positive)” or “safe (negative)” without contradicting the allergy test results (reaction present/absent) of the monitors.

By focusing on the very small constraint that the number of monitors \(M \le 20\), we can solve this efficiently within the time limit by combining the inclusion-exclusion principle with fast zeta transform (SOS DP).

---

Approach

1. Determining “Safe” Ingredients

First, for any monitor \(j\) with \(R_j = 0\) (no reaction), all ingredients consumed by that monitor must be “safe”. Therefore, these ingredients are uniquely determined to be “safe”.

On the other hand, ingredients that were never consumed by any monitor with \(R_j = 0\) remain undetermined at this point — they could be either “safe” or “allergen”. We will call these “allergen candidates”.

2. Contradiction Check

For monitors with \(R_j = 1\) (reaction present), at least one of the ingredients they consumed must be an allergen. If some monitor with \(R_j = 1\) consumed only ingredients that are all determined to be “safe”, then no matter how we assign the ingredients, a contradiction arises, and the answer is \(0\).

3. Rephrasing the Condition and Inclusion-Exclusion Principle

Let \(M'\) denote the number of monitors with \(R_j = 1\) (\(M' \le M \le 20\)). The condition to satisfy is that for all \(M'\) monitors, “at least one allergen is contained among the ingredients they consumed.”

Since directly counting configurations satisfying “at least one is included” is difficult, we use the inclusion-exclusion principle.

Let \(U\) be the set of monitors with \(R_j = 1\). Choose a subset \(T \subseteq U\), and consider the situation where “all monitors in \(T\) did not consume any allergen (= all of them end up with no reaction)”.

In this case, all ingredients consumed by monitors in \(T\) must be “safe”. Conversely, “allergen candidates” that are not consumed by any monitor in \(T\) can be freely assigned as either safe or allergen.

If we denote the number of such “freely assignable ingredients” as \(C(T)\), then the number of ways to assign them is \(2^{C(T)}\). By the inclusion-exclusion principle, the total number of valid combinations is computed as:

\[ \sum_{T \subseteq U} (-1)^{|T|} 2^{C(T)} \]

4. Speeding Up with Fast Zeta Transform (SOS DP)

Naively computing \(C(T)\) for all \(T \subseteq U\) would require scanning all ingredients for each \(T\), which would not fit within the time limit. Here we use the fast zeta transform (Sum Over Subsets DP).

For each “allergen candidate” ingredient \(i\), represent the set of monitors (with \(R_j = 1\)) that consume it as a bitmask \(mask[i]\). The condition that ingredient \(i\) is not consumed by any monitor in \(T\) can be expressed as:

\[ mask[i] \cap T = \emptyset \iff mask[i] \subseteq (U \setminus T) \]

Therefore, for mask \(S = U \setminus T\), if we can find “the number of ingredients \(i\) such that \(mask[i] \subseteq S\)”, this equals \(C(T)\). By recording the frequency of each \(mask[i]\) in an array and applying the fast zeta transform, we can compute the counts for all \(S\) simultaneously in \(O(M' 2^{M'})\).

---

Algorithm

1. Mark Safe Ingredients Mark all ingredients consumed by monitors with \(R_j = 0\) as “safe”.
2. Contradiction Check For monitors with \(R_j = 1\), if all of a monitor’s consumed ingredients are marked as safe, immediately output 0 and terminate.
3. Bitmask Construction Reassign IDs from \(0\) to \(M'-1\) to the monitors with \(R_j = 1\). For each ingredient \(i\) that is not marked as safe, create a bitmask mask[i] representing the set of monitor IDs that consume it, and increment the frequency array C[mask[i]].
4. Fast Zeta Transform (SOS DP) Apply the fast zeta transform to the frequency array C to create an array dp where each mask \(S\) contains “the total number of mask values that are subsets of \(S\)”.
5. Aggregation via Inclusion-Exclusion For all \(T \subseteq U\) (corresponding to S_mask in the code), obtain the number of freely assignable ingredients cnt = dp[U \setminus T], and compute \(2^{cnt}\). Depending on the parity of the number of elements in \(T\) (number of set bits), add or subtract \(2^{cnt}\) from the answer.

---

Complexity

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

  • Determining safe ingredients and constructing masks takes \(O(N + \sum k_j)\).
  • The fast zeta transform takes \(O(M' 2^{M'})\), and the inclusion-exclusion aggregation takes \(O(2^{M'})\).
  • Since \(N \le 2 \times 10^5, M \le 20\), the maximum number of operations is approximately \(2 \times 10^7\), which comfortably fits within the time limit.

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

  • Arrays for storing ingredient information use \(O(N)\), and the array for the fast zeta transform uses \(O(2^M)\) memory.

---

Implementation Notes

• Fast Zeta Transform Transition: By performing transitions in-place, we can implement it concisely while keeping memory usage low.

  
  for (int i = 0; i < M_prime; ++i) {
    for (int m = 0; m < (1 << M_prime); ++m) {
        if (m & (1 << i)) {
            dp[m] += dp[m ^ (1 << i)];
        }
    }
  }
  

• Utilizing Bit Operations: For determining the parity of the number of elements in set \(T\) (sign determination), using C++’s built-in function __builtin_popcount allows for fast processing.

  Source Code

#include <iostream>
#include <vector>
#include <atcoder/modint>

using namespace std;
using mint = atcoder::modint998244353;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<vector<int>> S(M);
    for (int j = 0; j < M; ++j) {
        int k;
        cin >> k;
        S[j].resize(k);
        for (int i = 0; i < k; ++i) {
            cin >> S[j][i];
        }
    }

    vector<int> R(M);
    for (int j = 0; j < M; ++j) {
        cin >> R[j];
    }

    vector<bool> is_safe(N + 1, false);
    for (int j = 0; j < M; ++j) {
        if (R[j] == 0) {
            for (int x : S[j]) {
                is_safe[x] = true;
            }
        }
    }

    vector<int> pos_monitors;
    for (int j = 0; j < M; ++j) {
        if (R[j] == 1) {
            pos_monitors.push_back(j);
        }
    }

    int M_prime = pos_monitors.size();

    // 矛盾チェック
    for (int j_prime = 0; j_prime < M_prime; ++j_prime) {
        int orig_j = pos_monitors[j_prime];
        bool has_unsafe = false;
        for (int x : S[orig_j]) {
            if (!is_safe[x]) {
                has_unsafe = true;
                break;
            }
        }
        if (!has_unsafe) {
            cout << 0 << "\n";
            return 0;
        }
    }

    vector<int> mask(N + 1, 0);
    for (int j_prime = 0; j_prime < M_prime; ++j_prime) {
        int orig_j = pos_monitors[j_prime];
        for (int x : S[orig_j]) {
            if (!is_safe[x]) {
                mask[x] |= (1 << j_prime);
            }
        }
    }

    vector<int> C(1 << M_prime, 0);
    for (int i = 1; i <= N; ++i) {
        if (!is_safe[i]) {
            C[mask[i]]++;
        }
    }

    vector<int> dp = C;
    for (int i = 0; i < M_prime; ++i) {
        for (int m = 0; m < (1 << M_prime); ++m) {
            if (m & (1 << i)) {
                dp[m] += dp[m ^ (1 << i)];
            }
        }
    }

    vector<mint> pow2(N + 1);
    pow2[0] = 1;
    for (int i = 1; i <= N; ++i) {
        pow2[i] = pow2[i - 1] * 2;
    }

    mint ans = 0;
    for (int S_mask = 0; S_mask < (1 << M_prime); ++S_mask) {
        int U = ((1 << M_prime) - 1) ^ S_mask;
        int cnt = dp[U];
        mint val = pow2[cnt];
        if (__builtin_popcount(S_mask) % 2 == 1) {
            ans -= val;
        } else {
            ans += val;
        }
    }

    cout << ans.val() << "\n";

    return 0;
}

---

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