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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

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

</details>

## 问题动机与核心知识

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

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

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

## 实现指南

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

## 精选例题 1：EXTENDED LIGHTS OUT

### 来源与题意

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

<details><summary>Hint 1</summary>每个按键是一个 0/1 变量，每盏灯给一条 XOR 方程。</details>
<details><summary>Hint 2</summary>方程系数包含该灯自己和四邻对应的按键。</details>

### Observations

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

### Editorial 与正确性证明

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

### 核心伪代码与附件

```text
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 附件](../../参考实现/10-高斯消元与CRT/POJ-1222.cpp)

## 精选例题 2：开关问题

### 来源与题意

- [POJ-1830 开关问题](https://vjudge.net/problem/POJ-1830)
- 给 $n$ 个开关初态、目标态及开关影响关系；每个开关至多操作一次，求方案数或报告不可达。

<details><summary>Hint 1</summary>第 i 个目标状态给一条 XOR 方程，右侧为初态 XOR 目标态。</details>
<details><summary>Hint 2</summary>每个开关默认影响自己；关系 `u v` 表示变量 u 出现在状态 v 的方程。</details>
<details><summary>Hint 3</summary>相容时答案为 $2^{n-rank}$。</details>

### Observations、Editorial 与证明

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

### 核心伪代码与附件

```text
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 附件](../../参考实现/10-高斯消元与CRT/POJ-1830.cpp)

## 精选例题 3：Widget Factory

### 来源与题意

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

<details><summary>Hint 1</summary>星期转为 0..6，右侧为 `(end-start+1) mod 7`。</details>
<details><summary>Hint 2</summary>7 是质数，非零主元可用 Fermat/枚举逆元。</details>

### 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))$，本题规模可行。

### 核心伪代码与附件

```text
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 附件](../../参考实现/10-高斯消元与CRT/POJ-2947.cpp)

## 扩展与联系

[CodeForces-1101G Zero XOR Subset](https://vjudge.net/problem/CodeForces-1101G) 把 XOR 线性无关转成线性基；线性基更适合在线插入和最大 XOR，高斯矩阵更适合显式方程与恢复解。

## 总结与自检

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

## 课后训练建议

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