Switches [AtCoder Beginner Contest 128 C]

https://atcoder.jp/contests/abc128/tasks/abc128_c

前提知識

• bit全探索

解説

https://atcoder.jp/contests/abc128/submissions/5778021

全探索対象を探すと、答えとなるON/OFFの組み合わせが2^N通りなので、全探索できそうな感じがある。
なので、全ての組み合わせについて、全部の電球がつくかどうかを判定し、全部つくなら答えをインクリメントする。
難しい問題に直面したときは、まずはどれを全探索するかを考えよう。

int N, M;
vector<int> S[10];
int P[10];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int k; cin >> k;
		rep(j, 0, k) {
			int s; cin >> s; s--;
			S[i].push_back(s);
		}
	}
	rep(i, 0, M) cin >> P[i];

	int ans = 0;
	rep(msk, 0, 1 << N) {
		int ok = 0;
		rep(m, 0, M) {
			int cnt = 0;
			fore(s, S[m]) if (msk & (1 << s)) cnt++;
			if (cnt % 2 == P[m]) ok++;
		}
		if (ok == M) ans++;
	}
	cout << ans << endl;
}