まず、\(R_j=0\) のモニターについては\(S_j\) に含まれる材料はすべてアレルギー物質を含みません。これを踏まえた上でアレルギー物質を含むか含まないか未確定の材料、\(R_j=1\) のモニターの情報のみを考えて実際に条件を満たす組み合せの数を求めます。便宜上\(R_j=0\) のモニターが存在しないとします。

包除原理を用いることを考えます。\(T\) を \(\{1,2,\ldots,M\}\) の部分集合とすると、\(c(T)\) を \(T\) のどの元の原材料の集合に含まれない材料の個数とします。

この時、答えは\(\displaystyle \sum_{T \subseteq \{1,2,\ldots,M\}}(-1)^{|T|} 2^{c(T)}\) となります。

この式において\(2^{c(T)}\) は、\(T\) に含まれるすべてのモニターについて、摂取した原材料の中にアレルギー原因物質が一つも存在しないような割り当ての個数になっています。これに対して適切に包除原理を用いて式変形を行うと上の通りとなります。

今度は \(c(T)\) を求める方法を考えます。原材料 \(x\) に対して \(A_x=\{j\mid x\notin S_j\}\) と置き、\(f(T)=|\{x\mid A_x=T\}|\) と定義します。 このとき、\(c(T)=\sum_{T \subseteq S}f(S)\) となります。

\(f(T)\) は\(O(NM+2^M)\) などで容易に計算でき、 \(c(T)\) は\(f(T)\) に対して高速ゼータ変換を行うことで \(\mathrm{O}(M2^M)\) で計算できます。アルゴリズムの解説はAtCoder Lecturesを参照してください。

したがって、全体で\(\mathrm{O}(M(N+2^M))\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> s(m);
    for (int i = 0; i < m; ++i) {
        int k;
        cin >> k;
        s[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> s[i][j];
            s[i][j]--;
        }
    }
    vector<int> safe(n, 0);
    vector<int> S(n, 0);
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
        int r;
        cin >> r;
        if (r == 0) {
            for (auto e : s[i]) safe[e] = 1;
        } else {
            for (auto e : s[i]) S[e] |= 1 << cnt;
            cnt++;
        }
    }
    int mask = (1 << cnt) - 1;
    vector<int> f(1 << cnt);
    for (int i = 0; i < n; ++i) {
        if (safe[i] == 0) f[mask ^ S[i]]++;
    }
    for (int i = 0; i < cnt; ++i) {
        for (int bit = 0; bit < (1 << cnt); ++bit) {
            if (!((bit >> i) & 1)) f[bit] += f[bit ^ (1 << i)];
        }
    }
    mint ans = 0;
    vector<mint> pow2(n + 1, 1);
    for (int i = 1; i <= n; ++i) pow2[i] = pow2[i - 1] * 2;
    for (int i = 0; i < (1 << cnt); ++i) {
        if (popcount((unsigned)i) % 2 == 0) {
            ans += pow2[f[i]];
        } else {
            ans -= pow2[f[i]];
        }
    }
    cout << ans.val() << endl;
}