abc128_c
電球M[i]に使うスイッチをビットで管理する
スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント
カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯
そういえば今回は書かなかったけどビットカウントをするときは
for(int i=bit; i; i&=(i-1) ) cnt++;
ってやるとスマート
#include<bits/stdc++.h>
using namespace std;
int n, m;
int s[19];
int p[19];
int ret_cnt(int x){
int ret = 0;
while(x){
ret += (x&1);
x = (x>>1);
}
return ret;
}
int main(){
cin >> n >> m;
for(int i=0;i<m;i++){
int k;
cin >> k;
for(int j=0;j<k;j++){
int ss;
cin >> ss;
s[i] |= (1<<(ss-1));
}
}
for(int i=0;i<m;i++) cin >> p[i];
int ans = 0;
for(int i=0;i<(1<<n);i++){
bool flg = true;
for(int j=0;j<m;j++){
int cnt = ret_cnt( (i&s[j]) );
if(p[j] != cnt%2) flg = false;
//cout << cnt << endl;
}
if(flg) ans++;
}
cout << ans << endl;
}