bit 全探索
問題概要
個のスイッチがある。スイッチによって
個の電球が点いたり消えたりする。
- 電球
は
個のスイッチに繋がっており、スイッチ
のうち on になっているスイッチの個数を 2 で割った余りが
に等しい時に点灯します。
全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。
制約
考えたこと
まず、 個のスイッチの on/off の状態は
通りある。それを決めれば、各電球が点灯するかどうかを求めることができる (ちょっと複雑だけども...)
さて問題は、その 通りの場合をどうやって探索し尽くすかだが、以下の記事の bit 全探索のところがぴったりである。
さて、スイッチの on/off がわかれば、
- 各電球
- それが偶数か奇数かによって、電球
という具合である。
#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
(スイッチ
とすると各電球に対する制約条件は
と書くことができるのだ。これによって、 本の制約の連立方程式となる。この解の個数を求めればよい。その求め方は以下の記事の通り。
#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; }
