掃き出し法 is 何
行基本変形で連立方程式を解いたりするやつ．
横ベクトルの集合の基底を求める作業とも解釈できる．
競プロでは xor に関する問題で使えることがある．
行基本変形を知っていますか？僕は知っています．
適当な行列・拡大行列 $A$ の行たちについて，次のような操作を行列の行基本変形という．
- ある行を $k\neq 0$ 倍する
- ある行にある行を足す
- ある行とある行を入れ替える
列についてもこういう変形はある．
掃き出し法では，行基本変形を用いて行簡約階段形に行列を変形する．
実家のような掃き出し法
アルゴリズムの説明が面倒なので，実際に変形の例を示す．
\left(
\begin{array}{cccc|c}
3 & 1 & 4 & 1 & 5\\
5 & 9 & 2 & 6 & 5\\
5 & 3 & 5 & 8 & 5\\
9 & 7 & 9 & 3 & 5
\end{array}
\right)
に掃き出し法のアルゴリズムを適用してみよう．
\left(
\begin{array}{cccc|c}
3 & 1 & 4 & 1 & 5\\
5 & 9 & 2 & 6 & 5\\
5 & 3 & 5 & 8 & 5\\
9 & 7 & 9 & 3 & 5
\end{array}
\right)\rightarrow
\left(
\begin{array}{cccc|c}
1 & \frac{1}{3} & \frac{4}{3} & \frac{1}{3} & \frac{5}{3}\\
5 & 9 & 2 & 6 & 5\\
5 & 3 & 5 & 8 & 5\\
9 & 7 & 9 & 3 & 5
\end{array}
\right)\rightarrow
\left(
\begin{array}{cccc|c}
1 & \frac{1}{3} & \frac{4}{3} & \frac{1}{3} & \frac{5}{3}\\
0 & \frac{22}{3} & \frac{-14}{3} & \frac{13}{3} & -\frac{10}{3}\\
0 & \frac{4}{3} & \frac{-5}{3} & \frac{19}{3} & -\frac{10}{3}\\
0 & 4 & -3 & 0 & -10
\end{array}
\right)\rightarrow
\left(
\begin{array}{cccc|c}
1 & \frac{1}{3} & \frac{4}{3} & \frac{1}{3} & \frac{5}{3}\\
0 & 1 & -\frac{7}{11} & \frac{13}{22} & -\frac{5}{11}\\
0 & \frac{4}{3} & -\frac{5}{3} & \frac{19}{3} & -\frac{10}{3}\\
0 & 4 & -3 & 0 & -10
\end{array}
\right)\\\rightarrow
\left(
\begin{array}{cccc|c}
1 & 0 & \frac{17}{11} & \frac{3}{22} & \frac{20}{11}\\
0 & 1 & -\frac{7}{11} & \frac{13}{22} & -\frac{5}{11}\\
0 & 0 & -\frac{9}{11} & \frac{61}{11} & -\frac{30}{11}\\
0 & 0 & -\frac{5}{11} & -\frac{26}{11} & -\frac{90}{11}
\end{array}
\right)\rightarrow
\left(
\begin{array}{cccc|c}
1 & 0 & \frac{17}{11} & \frac{3}{22} & \frac{20}{11}\\
0 & 1 & -\frac{7}{11} & \frac{13}{22} & -\frac{5}{11}\\
0 & 0 & 1 & -\frac{61}{9} & \frac{10}{3}\\
0 & 0 & -\frac{5}{11} & -\frac{26}{11} & -\frac{90}{11}
\end{array}
\right)\rightarrow
\left(
\begin{array}{cccc|c}
1 & 0 & 0 & \frac{191}{18} & -\frac{10}{3}\\
0 & 1 & 0 & -\frac{67}{18} & \frac{5}{3}\\
0 & 0 & 1 & -\frac{61}{9} & \frac{10}{3}\\
0 & 0 & 0 & -\frac{49}{9} & -\frac{20}{3}
\end{array}
\right)\rightarrow
\left(
\begin{array}{cccc|c}
1 & 0 & 0 & \frac{191}{18} & -\frac{10}{3}\\
0 & 1 & 0 & -\frac{67}{18} & \frac{5}{3}\\
0 & 0 & 1 & -\frac{61}{9} & \frac{10}{3}\\
0 & 0 & 0 & 1 & \frac{60}{49}
\end{array}
\right)\\\rightarrow
\left(
\begin{array}{cccc|c}
1 & 0 & 0 & 0 & -\frac{800}{49}\\
0 & 1 & 0 & 0 & \frac{305}{49}\\
0 & 0 & 1 & 0 & \frac{570}{49}\\
0 & 0 & 0 & 1 & \frac{60}{49}
\end{array}
\right)
アルゴリズム的には，目的の行の一番左の成分が非零になるように適当に行を交換して持ってきて，一行ずつ一番左の非零成分が $1$ になるように正規化し，他の行ではその列が $0$ になるように足し引きする，という作業になる．
正方行列なら，計算量は，行数・列数を $N$ として，$O(N^3)$ となる．
上のような拡大行列での掃き出し法は，線形方程式を解く作業と解釈することもできる．
それぞれの方程式の係数に対して行基本変形を行っても同値性が失われないのが重要である．
私は xor 好きです
次の問題を考える．
長さ $N$ の数列 $A$ が与えられる。集合 $U={x|x\in\mathbb{N},1\leq x\leq N}$ の空でない任意の部分集合 $S$ をとったとき、$S={k_1,k_2,\cdots k_l}$ として、$(A_{k_1} xor A_{k_2} xor \cdots xor A_{k_l})$ の最大値を求めよ。
bitwise xor は各ビットごとには独立に計算される．
また， ${a, b}$ から生成される集合と， ${a, a\ xor\ b}$ から生成される集合は等しい．
この性質より，掃き出し法を行っても，生成される集合は不変なので，掃き出し法が使える．
たとえば，$S={1, 2, 5, 6}$ のときは，次の行列を考える．
\left(
\begin{array}{cccc}
0 & 0 & 1\\
0 & 1 & 0\\
1 & 0 & 1\\
1 & 1 & 0
\end{array}
\right)
これを掃き出し法で処理すると，
\left(
\begin{array}{cccc}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 0
\end{array}
\right)
となる．このとき，列数 $W$ より下にある行の成分はすべて $0$ となり，高々 $W$ 個の行だけが非零である．
よって，先に述べた性質と，$x\ xor\ 0 = x$ より，高々 $W$ 個の行の組み合わせだけで，結果の集合を表現できる．
このように掃き出し法を作用させると，ある集合の部分集合の xor で生成される数を，基底を減らして少ない計算量で列挙できる．
xor の掃き出し法について，C[i] が元の集合の整数たちであるとき，実装は次のようになる．
const int MAX_DIGITS;
const int N;
int now = 0;
for (int i = MAX_DIGITS; i >= 0; i--) {
for (int j = now + 1; j < N; j++) {
if (C[j] & (1 << i)) {
std::swap(C[now], C[j]);
break;
}
}
if (!(C[now] & (1 << i))) continue;
rep(j, N) {
if (j != now && (C[j] & (1 << i))) C[j] ^= C[now];
}
now++;
}