ABC 128 C - Switches: bit演算を用いて解く

問題文 on と off の状態を持つ N 個の スイッチと、 M 個の電球があります。スイッチには 1 から N の、電球には 1 から M の番号がついています。

電球 i は k i 個のスイッチに繋がっており、スイッチ si1 , s i 2 , . . . , s i k i のうち on になっているスイッチの個数を 2 で割った余りが p i に等しい時に点灯します。

全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

自力での実装では、Sを問題文と同じように二次元の配列でもち、すべてのスイッチのパターンに対して、条件を満たすかどうかを判定していた。

しかし、この問題は『on/offの状態を持つ複数個のスイッチ』に対して『Sで表される参照すべきスイッチ』を選択し、それらの中で点灯しているものの個数が偶数か奇数を判定するというもので、

『『on/offの状態を持つ複数個のスイッチ』に対して『Sで表される参照すべきスイッチ』を選択する』の部分をビット演算を用いて行うことができる。

for (int i = 0; i < m; i++) {
    int k = nei();
    for (int j = 0; j < k; j++) {
        s[i] |= 1 << (nei() - 1);
    }
}

上記のように、Sで表される参照スイッチの条件を、00101100のように仮に表されるビット列でもつとする。これは例えば3番目と4番目のスイッチを参照する条件を表す時

1. S[i]を0で初期化
2. 1を2(=3-1)左にビットシフトする
3. S[i]と↑で論理和を取る
4. 1を3(=4-1)左にビットシフトする
5. S[i]と↑で論理和を取る

とすることで 11000(=24)が得られる。

これに、例えばスイッチが5個なら、int max = 1 << 5 (= 100000 = 32)として、for文で回して、論理積を撮って、bitCountをとってやれば良い。

細かいテクニックとして、2で割ったあまりは & 1をすることで取れる。

for (int i = 0; i < max; i++) {
    for (int j = 0; j < m; j++) {
    if ((Integer.bitCount(bs[j] & i) & 1) != ps[j]) 
        break;
    }
}

最速回答を見て勉強すると学ぶことが多いです。回答者の方には感謝しか無い。