lessons/课程/10-高斯消元与CRT/01-高斯消元秩解空间与XOR系统.md

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

本节目标

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

前置知识与课前自测

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

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

答案

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 附件

扩展与联系

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

总结与自检

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

课后训练建议

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