01 矩阵反转每个位置的秩

http://qoj.ac/contest/750/problem/3319

题意

给定 \(n\times m\) 的 01 矩阵 \(A\)，求反转每个位置后，新矩阵的秩。

数据范围：\(n,m\le 10^3\)。

分析

记 \(A_i\) 为 \(A\) 的第 \(i\) 行，设 \(H(A_i,j)\) 为把 \(A_i\) 的第 \(j\) 列取反得到的向量。设 \(F(A,i,j)\) 为把 \(A_{i,j}\) 取反得到的矩阵，\(G(A,i)\) 为把 \(A\) 的第 \(i\) 行删去得到的矩阵。我们只需算出以下 3 个值既可间接算出答案：

• \(Rank(A)\)
• \(Rank(A)-Rank(G(A,i))\)
• \(Rank(F(A,i,j))-Rank(G(A,i))\)

由于 \(A\) 是 01 矩阵，计算 \(Rank(A)\) 可以用 bitset 优化，时间复杂度为 \(O(\frac{n^3}{w})\)。

要计算 \(Rank(A)-Rank(G(A,i))\)，我们只需判断 \(G(A,i)\) 的所有行向量张成的线性空间是否包含 \(A_i\)。将该命题称为 \(P_i\)，则 \(Rank(A)-Rank(G(A,i))+[P_i]=1\)。

称 \(A\) 的一个行子集满足性质 \(X\)，当且仅当其中所有行向量的异或和为 \(0\)。那么 \(P_i\) 成立等价于存在一个满足性质 \(X\) 的行子集包含 \(i\)。注意到任意 2 个满足性质 \(X\) 的行子集的异或仍然满足性质 \(X\)，因此只需求出满足性质 \(X\) 的行子集的一组基，这样，\(P_i\) 成立等价于 \(i\) 在所有基的并集（设为 \(S\)）中。而这组基的求解过程正是将 \(A\) 的每行插入线性基，若插入失败就添加一个行子集。

同理，要计算 \(Rank(F(A,i,j))-Rank(G(A,i))\)，只需判断 \(G(A,i)\) 的所有行向量张成的线性空间是否包含 \(H(A_i,j)\)。将命题称为 \(Q_{i,j}\)，则 \(Rank(F(A,i,j))-Rank(G(A,i))+Q_{i,j}=1\)。

称 \(A\) 的一个行子集满足性质 \(Y_j\)，当且仅当其中所有行向量的异或和为：
\(\left[\underbrace{0,\cdots,0}_{j-1},1,0,\cdots,0\right]\)

注意到任意两个满足性质 \(Y_j\) 的行子集的异或满足性质 \(X\)。设使 \(Q_{i,j}\) 成立的 \(i\) 构成的集合为 \(T_j\)。那么分 2 种情况：

1. 若不存在满足性质 \(Y_j\) 的行子集，\(T_j=\varnothing\)。
2. 否则，设任意一个满足性质 \(Y_j\) 的行子集为 \(y_j\)，那么 \(T_j=S\cup \{y_j\}\)。

因此我们只需求出 \(y_j\)，直接把向量放到线性基里消元既可。总时间复杂度仍为 \(O(\frac{n^3}{w})\)。