概要

この問題は、モニターのアレルギー検査結果（反応あり・なし）と矛盾しないように、各原材料が「アレルギー原因物質（陽性）」か「安全（陰性）」かを決める組み合わせの総数を求める問題です。

モニターの数 \(M \le 20\) という制約が非常に小さいことに着目し、包除原理と高速ゼータ変換（SOS DP）を組み合わせることで、制限時間内に高速に解くことができます。

---

考察

1. 「安全」な原材料の確定

まず、\(R_j = 0\)（反応なし）であるモニター \(j\) が摂取した原材料は、すべて「安全」でなければなりません。 したがって、これらの原材料は「安全」であると一意に確定します。

一方、一度も \(R_j = 0\) のモニターに摂取されなかった原材料は、「安全」か「アレルギー原因物質」のどちらであるか、現時点では未確定です。これらを「原因物質の候補」と呼ぶことにします。

2. 矛盾のチェック

\(R_j = 1\)（反応あり）であるモニターは、摂取した原材料の中に少なくとも1つはアレルギー原因物質が含まれている必要があります。 もし、ある \(R_j = 1\) のモニターが摂取した原材料がすべて「安全」と確定している場合、どのように原材料を決めても矛盾が生じるため、答えは \(0\) 通りとなります。

3. 条件の言い換えと包除原理

\(R_j = 1\) であるモニターの数を \(M'\) とします（\(M' \le M \le 20\)）。 満たすべき条件は、これら \(M'\) 人のモニター全員について「摂取した原材料の中に少なくとも1つアレルギー原因物質が含まれる」ことです。

「少なくとも1つ含まれる」という条件を直接数え上げるのは難しいため、包除原理を利用します。

\(R_j = 1\) であるモニターの集合を \(U\) とします。\(U\) の部分集合 \(T \subseteq U\) を選び、「\(T\) に含まれるすべてのモニターがアレルギー原因物質を1つも摂取していない（＝全員反応なしになってしまう）」という状況を考えます。

このとき、\(T\) に含まれるモニターが摂取する原材料はすべて「安全」でなければなりません。 逆に言えば、\(T\) に含まれるどのモニターにも摂取されない「原因物質の候補」については、安全か原因物質かを自由に決めることができます。

このような「自由に決められる原材料」の個数を \(C(T)\) とすると、その割り当て方は \(2^{C(T)}\) 通りとなります。 包除原理により、求める組み合わせの総数は以下の式で計算できます。

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

4. 高速ゼータ変換（SOS DP）による高速化

すべての \(T \subseteq U\) について \(C(T)\) を愚直に求めると、各 \(T\) について原材料を走査する必要があり、実行時間制限に間に合いません。ここで高速ゼータ変換（Sum Over Subsets DP）を使用します。

各「原因物質の候補」である原材料 \(i\) について、それを含んでいるモニター（\(R_j = 1\) のもの）の集合をビットマスク \(mask[i]\) で表します。 原材料 \(i\) が \(T\) に含まれるどのモニターにも摂取されない条件は、以下のように表せます。

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

したがって、マスク \(S = U \setminus T\) に対して、「\(mask[i] \subseteq S\) となる原材料 \(i\) の個数」が求まれば、それが \(C(T)\) と一致します。 これは、各 \(mask[i]\) の出現頻度を記録した配列に対して、高速ゼータ変換を行うことで、すべての \(S\) に対する個数を \(O(M' 2^{M'})\) でまとめて計算できます。

---

アルゴリズム

1. 安全な原材料のマーク \(R_j = 0\) であるモニターが摂取したすべての原材料を「安全」とマークします。
2. 矛盾チェック \(R_j = 1\) であるモニターについて、摂取した原材料がすべて安全マークされているものがあれば、即座に 0 を出力して終了します。
3. ビットマスクの作成 \(R_j = 1\) であるモニターに \(0\) から \(M'-1\) までの ID を振り直します。 安全マークされていない各原材料 \(i\) について、自身を摂取するモニターの ID の集合を表すビットマスク mask[i] を作成し、頻度配列 C[mask[i]] をインクリメントします。
4. 高速ゼータ変換（SOS DP） 頻度配列 C に対して高速ゼータ変換を行い、各マスク \(S\) について「\(S\) の部分集合であるような mask の総数」を求めた配列 dp を作成します。
5. 包除原理による集計 すべての \(T \subseteq U\)（コード内では S_mask に相当）について、自由に決められる原材料の数 cnt = dp[U \setminus T] を取得し、\(2^{cnt}\) を計算します。 \(T\) の要素数（立っているビットの数）の偶奇に応じて、答えに \(2^{cnt}\) を足し引きします。

---

計算量

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

  • 安全な原材料の判定やマスクの作成に \(O(N + \sum k_j)\) かかります。
  • 高速ゼータ変換に \(O(M' 2^{M'})\)、包除原理の集計に \(O(2^{M'})\) かかります。
  • \(N \le 2 \times 10^5, M \le 20\) であるため、最大でも約 \(2 \times 10^7\) 回の演算となり、実行時間制限に余裕で間に合います。

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

  • 原材料の情報を格納する配列に \(O(N)\)、高速ゼータ変換用の配列に \(O(2^M)\) のメモリを使用します。

---

実装のポイント

• 高速ゼータ変換の遷移: in-place で遷移を行うことで、メモリ使用量を抑えつつ簡潔に実装できます。

  
  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)];
        }
    }
  }
  

• ビット演算の活用: 集合 \(T\) の要素数の偶奇（符号の決定）には、C++の組み込み関数である __builtin_popcount を使用することで高速に処理できます。

  ソースコード

#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;
}

---

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