abc128_c

電球M[i]に使うスイッチをビットで管理する

スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント

カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯

そういえば今回は書かなかったけどビットカウントをするときは

for( 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*1;

            if(p[j] != cnt%2) flg = false;

            //cout << cnt << endl;

        }

        if(flg) ans++;

    }

    cout << ans << endl;

   

}

*1:i&s[j]