AtCoder ABC 128 C - Switches (緑色, 300 点)

bit 全探索

問題へのリンク

問題概要

個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。

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

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

制約

• 

考えたこと

まず、 個のスイッチの on/off の状態は 通りある。それを決めれば、各電球が点灯するかどうかを求めることができる (ちょっと複雑だけども...)

さて問題は、その 通りの場合をどうやって探索し尽くすかだが、以下の記事の bit 全探索のところがぴったりである。

qiita.com

さて、スイッチの on/off がわかれば、

• 各電球 について、 のうち、on のスイッチが何個かを数える
• それが偶数か奇数かによって、電球 が点いているかどうかがわかる

という具合である。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int> > s(M);
    for (int i = 0; i < M; ++i) {
        int k; cin >> k;
        for (int j = 0; j < k; ++j) {
            int a; cin >> a; --a;
            s[i].push_back(a);
        }
    }
    vector<int> p(M);
    for (int i = 0; i < M; ++i) cin >> p[i];
    
    long long res = 0;
    for (int bit = 0; bit < (1<<N); ++bit) {
        bool ok = true;
        for (int i = 0; i < M; ++i) {
            int con = 0;
            for (auto v : s[i]) {
                if (bit & (1<<v)) ++con;
            }
            if (con % 2 != p[i]) ok = false;
        }
        if (ok) ++res;
    }
    cout << res << endl;
}

番外編の別解: F2 体上の連立一次方程式の解の個数

番外編として、実はこの問題は

• 

とかでも解くことができる。連立一次方程式の解の個数に帰着させるのだ。今回の問題は

• or 　(スイッチ が点いているかどうか)

とすると各電球に対する制約条件は

• 　

と書くことができるのだ。これによって、 本の制約の連立方程式となる。この解の個数を求めればよい。その求め方は以下の記事の通り。

drken1215.hatenablog.com

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

const int MAX_ROW = 510; // to be set appropriately
const int MAX_COL = 510; // to be set appropriately
struct BitMatrix {
    int H, W;
    bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
    inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};

int GaussJordan(BitMatrix &A, bool is_extended = false) {
    int rank = 0;
    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = rank; row < A.H; ++row) {
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(A[pivot], A[rank]);
        for (int row = 0; row < A.H; ++row) {
            if (row != rank && A[row][col]) A[row] ^= A[rank];
        }
        ++rank;
    }
    return rank;
}

int linear_equation(BitMatrix A, vector<int> b, vector<int> &res) {
    int m = A.H, n = A.W;
    BitMatrix M(m, n + 1);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) M[i][j] = A[i][j];
        M[i][n] = b[i];
    }
    int rank = GaussJordan(M, true);

    // check if it has no solution
    for (int row = rank; row < m; ++row) if (M[row][n]) return -1;

    // answer
    res.assign(n, 0);
    for (int i = 0; i < rank; ++i) res[i] = M[i][n];
    return rank;
}


int main() {
    int N, M; cin >> N >> M;
    BitMatrix A(M, N);
    vector<int> b(M);
    for (int i = 0; i < M; ++i) {
        int k; cin >> k;
        for (int j = 0; j < k; ++j) {
            int s; cin >> s; --s;
            A[i][s] = 1;
        }
    }
    for (int i = 0; i < M; ++i) {
        int p; cin >> p;
        b[i] = p;
    }
    vector<int> res;
    int rank = linear_equation(A, b, res);
    if (rank == -1) cout << 0 << endl;
    else cout << (1<<(N-rank)) << endl;
}