高斯消元：秩、解空间与不同数域

本节目标

能把开关/线性关系写成增广矩阵，在实数、有限域和 XOR 域中选择正确消元运算；判断无解、唯一解、多解，并由秩计算自由变量数。

前置知识与课前自测

前置：线性方程、模逆、异或。

某行系数全 0、常数非 0 表示什么？
$n$ 个变量、系数矩阵秩为 $r$ 且系统相容时，XOR 解数是多少？
模合数时是否每个非零主元都有逆元？

答案

1. 矛盾方程 $0=c$，系统无解。 2. $2^{n-r}$。 3. 不是；只有与模数互质的元素可逆，普通有限域消元不能直接照搬。

问题动机与核心知识

高斯消元的本质是做不改变解集的初等行变换，逐列选择主元并消去其他行。真正需要记录的不是“消到第几行”，而是秩：

出现矛盾行：无解；
相容且 rank=variables：唯一解；
相容且秩更小：存在自由变量，多解。

运算域决定细节：实数要选绝对值较大主元并用 eps；模质数用逆元；XOR 域中加减都是 XOR，非零主元只有 1，可用 bitset 加速。

实现指南

行数与变量数可不同，循环条件同时检查 row<equations 与列范围。
消元后先扫矛盾行，再由 rank 判多解。
模运算每次归一到 [0,p)；负数修正。
XOR 解计数可能很大，按题意选择大整数或保证范围。

精选例题 1：EXTENDED LIGHTS OUT

来源与题意

POJ-1222 EXTENDED LIGHTS OUT，Greater New York 2002
固定 $5\times6$ 灯阵；按一格会翻转自己和上下左右，给初态，输出一组使所有灯熄灭的按键方案。

Hint 1

每个按键是一个 0/1 变量，每盏灯给一条 XOR 方程。

Hint 2

方程系数包含该灯自己和四邻对应的按键。

Observations

同一按键按两次抵消，所以只关心奇偶，天然位于 $\mathbb F_2$。
按键与灯各 30 个，直接消元无需搜索 $2^{30}$。
输出矩阵下标必须与变量编号保持同一映射。

Editorial 与正确性证明

令 $x_{r,c}$ 表示是否按格子。灯 $(r,c)$ 最终状态等于初态 XOR 自己及四邻按键，要求为 0，得到 30 元 XOR 方程。对增广矩阵做 Gauss-Jordan；题目数据保证可输出方案。每个方程恰表达一盏灯最终熄灭，解向量与按键方案双向等价。

核心伪代码与附件

for each lamp cell:
    equation has variables at self and four neighbors
    rhs = initial lamp state
for each variable column:
    find pivot row with bit 1; swap
    XOR pivot row into every other row having this bit
output solved variable bits as 5x6 grid

完整 C++17 附件

精选例题 2：开关问题

来源与题意

POJ-1830 开关问题
给 $n$ 个开关初态、目标态及开关影响关系；每个开关至多操作一次，求方案数或报告不可达。

Hint 1

第 i 个目标状态给一条 XOR 方程，右侧为初态 XOR 目标态。

Hint 2

每个开关默认影响自己；关系 `u v` 表示变量 u 出现在状态 v 的方程。

Hint 3

相容时答案为 $2^{n-rank}$。

Observations、Editorial 与证明

消元只需行阶梯形。若零系数行 RHS 为 1 则无解；否则每个非主元变量可独立取 0/1，主元由它们唯一确定，所以方案数为 $2^{n-rank}$。方程逐状态精确表达所有影响 XOR，故解与操作集合一一对应。

核心伪代码与附件

matrix[target_switch][pressed_switch] = whether press affects target
rhs = initial XOR target
rank = XOR_Gaussian_elimination(matrix)
if contradictory row exists: print unreachable
else: print 2 ** (n - rank)

完整 C++17 附件

精选例题 3：Widget Factory

来源与题意

POJ-2947 Widget Factory，Central Europe 2005
$n$ 个未知生产天数、$m$ 条星期约束；每条给若干工件及起止星期，判断模 7 方程组无解、多解或唯一，唯一时把余数映射到 3..9 输出。

Hint 1

星期转为 0..6，右侧为 `(end-start+1) mod 7`。

Hint 2

7 是质数，非零主元可用 Fermat/枚举逆元。

Observations

“星期”只提供模 7 信息，不能在整数/实数上消元。
同一变量在一条记录中出现多次时系数需累加模 7。
唯一余数 0,1,2 分别以 7,8,9 输出，符合允许天数 3..9。

Editorial 与正确性证明

建立 $m\times(n+1)$ 模 7 增广矩阵。逐列找非零主元，乘逆元归一，并消去其他行。初等行变换在域 $\mathbb F_7$ 上可逆，因此保持解集；矛盾行、秩与变量数分别给出三种结论。唯一解按题目代表元映射输出。

复杂度 $O(mn\min(m,n))$，本题规模可行。

核心伪代码与附件

build equations modulo 7
for each variable column:
    select nonzero pivot
    normalize pivot by modular inverse
    eliminate this column from all other rows
check contradiction; compare rank with variable count

完整 C++17 附件

扩展与联系

高阶例题：XOR Neighbors

来源信息与题意

VJudge：AtCoder-abc366_g XOR Neighbors
原题：AtCoder Beginner Contest 366 G
难度：ABC 600 分；考点：邻接矩阵、XOR 零空间、基向量编码

给定 $1\le N\le60$ 的简单无向图。给每个点 $v$ 写一个 $1\le X_v<2^{60}$ 的整数，使每个非孤立点的所有邻点所写整数 XOR 为 0；判断是否存在并构造。

Hint 1：拆开整数的每个二进制位

固定一位，令 $x_v$ 表示点 $v$ 在该位是否为 1。邻点 XOR 为 0 等价于邻接矩阵 $A$ 满足 $Ax=0$（在 $\mathbb F_2$ 上）。

Hint 2：为什么一个零空间向量通常不够

题目要求每个 $X_v$ 非零；单个非零解可能在某些坐标仍是 0。能否把零空间的多组解分别放在不同二进制位？

Hint 3：何时某个坐标永远为 0

求出 $\ker A$ 的一组基。若点 $v$ 在每个基向量上的坐标都为 0，则任意线性组合在该坐标也为 0；反之只要某个基向量覆盖它，就能把对应基编号编码进 $X_v$。

Observations

直接给点分配整数看似有巨大值域；按位拆开后，每一位都是同一个齐次 XOR 方程组，数值大小只是允许我们并排放最多 60 个解。
只问是否有非零零空间不够。例如某个点可能在所有零空间向量中恒为 0，即使其他坐标可以非零，仍违反 $X_v\ge1$。
枚举所有零空间向量是 $2^{N-rank}$；基已经完整描述每个坐标是否可能为 1。把第 $k$ 个基向量放到整数的第 $k$ 位，就一次性保留了全部覆盖信息。
零空间维数不超过 $N\le60$，恰好能装入题目允许的 60 位；这是数值上界与代数维数的关键契约。

Editorial、正确性与复杂度

以图的邻接矩阵 $A$ 为系数矩阵。对每个二进制位 $k$，所有点该位组成列向量 $x^{(k)}$，则点 $v$ 的邻点 XOR 在该位为 $(Ax^{(k)})_v$。所以一个合法位必须属于 $\ker A$；孤立点对应全零行，条件自动成立。

Gauss-Jordan 消元后，每个自由变量取 1、其他自由变量取 0，并回代主元变量，得到零空间基 $b0,\ldots,b{d-1}$。构造

$$ Xv=\sum{k=0}^{d-1} b_k[v]2^k. $$

每一位 $b_k$ 都满足 $Ab_k=0$，故所有非孤立点的邻点 XOR 为 0。若所有 $X_v>0$，范围也满足 $X_v<2^d\le2^{60}$，构造合法。

反过来，若某个 $X_v=0$，说明每个基向量在坐标 $v$ 都为 0。基张成整个零空间，所以任意合法位向量在该坐标都为 0，任何整数构造都只能令该点为 0，不可能有解。因此最后的非零检查既充分又必要。

用 64 位整数存每行，消元时间 $O(N^3/64)$ 的位运算实现（按当前逐行写法可视为 $O(N^3)$、但 $N\le60$），空间 $O(N)$ 个机器字。

核心伪代码与参考实现附件

A = adjacency matrix over GF(2)
RREF(A); record pivot columns

basis = empty
for every free column f:
    vector x has x[f] = 1
    use RREF rows to recover every pivot coordinate of x
    append x to basis

for vertex v:
    X[v] = bitmask of basis indices k with basis[k][v] == 1
if some X[v] == 0: output No
else: output Yes and all X[v]

完整 GNU C++17 参考实现：AtCoder-abc366_g.cpp

实现细节、复盘与变式

无向边要在邻接矩阵的两个对称位置置 1；题目保证简单图，但用 XOR 写入也能避免重复边被误计两次。
N=60 时最高使用位为 59，1ULL<<59 合法；不要用有符号 1LL<<60 处理边界。
RREF 行与主元列必须一一对应，构造自由变量基时才能直接恢复主元坐标。
识别信号是“所有邻居的 XOR”而不是路径 XOR；前者直接是邻接矩阵乘向量，后者通常进入势能与环空间。
若整数上界只允许 $k<\dim\ker A$ 位，不能机械放下整组基；那会变成“用至多 $k$ 个零空间向量覆盖所有坐标”的额外组合问题。

扩展与联系

CodeForces-1101G Zero XOR Subset 把 XOR 线性无关转成线性基；线性基更适合在线插入和最大 XOR，高斯矩阵更适合显式方程与恢复解。

总结与自检

rank 如何区分唯一/多解？
XOR 域的行加法是什么？
为什么模 7 可除以非零主元？
模合数时普通写法在哪里失效？

课后训练建议

用枚举所有 $2^n$ 变量对拍 XOR 消元；模 7 题随机生成解再造方程，核对恢复。调试优先打印 rank、主元列和矛盾行，而不是只看最终答案。

01-高斯消元秩解空间与XOR系统.md 10 KB История Исходник

高斯消元：秩、解空间与不同数域

本节目标

前置知识与课前自测

问题动机与核心知识

实现指南

精选例题 1：EXTENDED LIGHTS OUT

来源与题意

Observations

Editorial 与正确性证明

核心伪代码与附件

精选例题 2：开关问题

来源与题意

Observations、Editorial 与证明

核心伪代码与附件

精选例题 3：Widget Factory

来源与题意

Observations

Editorial 与正确性证明

核心伪代码与附件

扩展与联系

高阶例题：XOR Neighbors

来源信息与题意

Observations

Editorial、正确性与复杂度

核心伪代码与参考实现附件

实现细节、复盘与变式

扩展与联系

总结与自检

课后训练建议

01-高斯消元秩解空间与XOR系统.md 10 KB

История Исходник