問題概要
$N$ 個の電球と $N$ 個のスイッチがある。スイッチは1つに限らず複数の電球に接続していることがあり、この情報は入力で与えられる。この電球は、接続してるスイッチのうち奇数個のスイッチがonになっている場合に限り点灯する。
全ての電球について、その電球のみが点灯するようなonにするスイッチの選び方を一つ求めよ。ただし1つでも構築不可能であるなら -1 のみを出力せよ。
制約
$ 1 \leqq N \leqq 500$
解法
行列 $A$ を
- $i$ 番目の電球に $j$ 番目のスイッチが接続しているなら $A_{i, j}=1$
- そうでないなら $A_{i, j}=0$
と定める。
例として1番目の電球のみを点灯させたい場合を考えると、
$$ \begin{aligned} &A _ {1,1} x _ {1}+A _ {2,1} x _ {2}+A _ {3,1} x _ {3}+\ldots+A _ {n, 1} x _ {n}=1\bmod 2\\ &A _ {1,2} x _ {1}+A _ {2,2} x _ {2}+A _ {3,2} x _ {3}+\ldots+A _ {n, 2} x _ {n}=0\bmod 2\\ &A _ {1,3} x _ {1}+A _ {2,3} x _ {2}+A _ {3,3} x _ {3}+\ldots+A _ {n, 3} x _ {n}=0\bmod 2\\ &\ldots \\ &A _ {1, n} x _ {1}+A _ {2, n} x _ {2}+A _ {3, n} x _ {3}+\ldots+A _ {n, n} x _ {n}=0\bmod 2 \end{aligned} $$
を満たすような $x _ {i}$ を求めて、$x _ {i}=1$ を満たす $i$ の集合が求めたい答えとなる。
これを電球毎に素朴に $N$ 回繰り返して求解すると $O(N^{4})$ 解が得られる。
ここで1つの重要な性質があり、題意を満たすような解が存在することと、行列 $A$ が正則行列であることが必要十分条件となる。
これはもし問題文の条件を満たすならば、可能な $2^{n}$ の電球状態それぞれに対応するスイッチの押し方が存在することから言える。
従って正則行列の判定を行い、逆行列 $A^{-1}$ を求め、N回 $x=A^{-1} b$ となる $x$ を求めれば良い。
01からなる行列なので実際に掛け算をしなくても簡単に求めることができ、上の説明では入力の転置を取った行列を用いていたが、話はもっと簡略化できて単純に入力で与えられた行列の逆行列がそのまま答えと一致する。
計算量は全体で $O(N^{3})$ bitsetを用いることで更に高速化できる。
実装
#include <bits/stdc++.h> using namespace std; typedef long long int ll; const int MAXN=500; bitset<MAXN> A[MAXN],basis[MAXN],inv[MAXN]; int main(){ int n; cin >> n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int x; cin >> x; if(x)A[i][j]=1; } } for(int i=0;i<n;i++){ bitset<MAXN> v=A[i]; bitset<MAXN> w; w[i]=1; bool ok=false; for(int j=0;j<n;j++){ if(v[j]){ if(!basis[j][j]){ basis[j]=v; inv[j]=w; ok=true; break; } else{ v^=basis[j]; w^=inv[j]; } } } if(!ok){ printf("-1\n"); return 0; } } for(int i=n-1;i>=0;i--){ for(int j=i+1;j<n;j++){ if(basis[i][j]){ basis[i]^=basis[j]; inv[i]^=inv[j]; } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(inv[i][j])printf("%d ",j+1); } printf("\n"); } }
