课前零食：开关与错开的时钟

这是一份双拼零食。前半杯问“很多开关怎样一起满足条件”，后半杯问“两个不同周期什么时候再次对齐”。它们表面不像，骨子里都在做一件事：保留约束、消掉多余自由度。

本节目标

学完后，你能：

把“按一次算翻转”翻译成 XOR 线性方程；
解释高斯消元的行变换为什么不改变解集，并用秩判断无解/多解；
把同余 $x\equiv a\pmod m$ 读成一个按周期响的时钟；
手推两个同余条件的合并，并知道非互质模数何时冲突。

前置知识与课前自测

前置：方程、模运算、XOR、最大公因数。

两次按同一个翻转开关后，灯的状态为什么回到原处？
方程 $x+y=1$ 与 $x+y=1$ 写两遍，会提供两条独立信息吗？
$x\equiv1\pmod4$ 与 $x\equiv2\pmod6$ 有公共解吗？

答案

1. 在 XOR 世界中 $1\oplus1=0$。2. 不会，第二行完全重复。3. 没有；两边对 $\gcd(4,6)=2$ 的余数不同，分别是 1 和 0。

互动规则：每个符号都要翻译回一个约束

这节分成两个工作台。开关台上，x_i=0/1 不是抽象字母，而是“第 i 个开关按/不按”；每一行方程是一盏灯的要求。时钟台上，x≡a (mod m) 不是公式，而是“从 a 开始每隔 m 出现一次”的时间点列。

每次变形都要写一张收据：变形前哪些答案可行，变形后是否恰好还是这些答案？不能回答这句时，先不要做下一步消元或合并。

从零搭框架：先枚举小世界，再把重复候选压成约束

第 0 步：三个开关时，人脑能枚举什么

令 x1,x2,x3 表示三个开关是否按。要求是：

$$ x_1\oplus x_2=1,\qquad x_2\oplus x_3=0. $$

请列出 000 到 111 的八种按法，先筛第一条约束，再筛第二条。把留下的按法写出来。

停顿 0：如果变成 30 个开关，枚举从哪里爆炸？两条方程里哪一个变量出现了两次、可能被消掉？

展开：从候选表到行

合法按法有 `100` 与 `011`。30 个开关有 $2^{30}$ 种候选，不能逐份测试。两式都含 `x2`，把两边同时 XOR 就得到 `x1 xor x3 = 1`，并没有列举任何新候选，却把共同变量消掉。

第 1 步：先验证“行 XOR 行”没有偷偷改题

给第一行取一组满足它的值，给第二行也取同一组值。若两行都成立，把等式左右各 XOR 一次，结果一定成立吗？反过来，若第一行与“第一 XOR 第二行”成立，能否再 XOR 第一行恢复第二行？

停顿 1：这两句构成了什么样的双向证明？为什么它比“消元看起来合理”更可靠？

展开：初等行变换保留解集

两行同时成立时 XOR 后成立；已知第一行和 XOR 后的行，再 XOR 第一行便恢复第二行。因此替换一行不会增解也不会漏解，是解集等价变换。交换两行也只是换顺序。消元每一步都应靠这样的可逆/等价理由站住。

第 2 步：让主元和秩从纸上的阶梯长出来

把三行写成增广矩阵：

1 1 0 | 1
0 1 1 | 0
1 0 1 | 1

先在第 1 列找一个 1 当主元，再用它 XOR 掉第 3 行第 1 列；随后处理第 2 列。每处理一列，在纸上圈出一个“首次独立约束”。

停顿 2：最后若出现 0 0 0 | 1，它翻译成什么人话？若某列从头到尾没主元，哪个变量得到什么自由？

展开：秩是独立约束数

全 0 系数配 1 是 `0=1`，无解；没有主元的列对应可自由选择的变量。相容时，秩等于独立方程数；变量数减秩就是自由度。XOR 域中主元非零只能是 1，所以用整行 XOR 即可消去。

第 3 步：换到时钟台，先真的把时间点列出来

写两行时间：

x ≡ 1 (mod 4): 1, 5, 9, 13, ...
x ≡ 3 (mod 6): 3, 9, 15, ...

请圈出第一次相交，再写出下一次相交。然后把第一个条件写成 x=1+4t，代入第二个条件。

停顿 3：为什么不必继续从 0、1、2、3……逐个试？新变量 t 代表什么动作？

展开：CRT 也在压缩候选表

相交为 9、21，周期为 12。`t` 表示沿第一个时钟每跳一次 4 的次数；代入把“所有满足第一个条件的候选”压成一个关于 t 的同余。求 t 后就一次性得到共同候选，而不是枚举时间线。

第 4 步：非互质时先检查两只时钟能否对齐

比较：

$$ x\equiv1\pmod4,\ x\equiv3\pmod6 $$

与：

$$ x\equiv1\pmod4,\ x\equiv2\pmod6. $$

请分别把两边对 2 的余数写出来。为什么第一对有机会、第二对永远无机会？

展开：gcd 是共同刻度

模 4 与模 6 都按 2 的共同刻度重复。第一对余数均为 1，兼容；第二对一个为 1、一个为 0，冲突。一般先检查 $g=\gcd(m,n)$ 是否整除 $b-a$，通过后才能除掉共同因子、在互质模数下求逆。

第 5 步：写出两条框架主线

工作台	原始暴力对象	新状态/摘要	合法变形	最终判断
开关
时钟

展开：它们都在维护解集合

开关从 $2^n$ 赋值到矩阵行与主元，靠等价行变换，判断无解/秩/自由度；时钟从一长串候选时间到“余数 + 模数”，靠兼容合并，判断无解或新的周期。两者不必硬说成同一算法，但都要求每一步不改变可行解集合。

问题动机：枚举按法和枚举日期都长得很快

有 $n$ 个开关时，“按/不按”已有 $2^n$ 种组合；有两个周期很大的时钟时，从 0 开始逐个试时间也可能要等很久。两类暴力都在重复探索同一个约束空间。我们要学会合并约束，而不是逐个候选试探。

步步式引导

1. 开关：把“是否按”当成变量

令 $x_i\in{0,1}$ 表示第 $i$ 个开关是否按。某盏灯被若干开关影响，要求最终翻成目标状态，就是这些 $x_i$ 的 XOR 等于 0 或 1。例如：

$$ x_1\oplus x_2=1,\qquad x_2\oplus x_3=0. $$

两条方程 XOR 在一起相当于“左右两边同时加同一式子”，解集不变，却能消掉共同变量。交换方程、用一行 XOR 另一行，都是不改变解集的合法行变换。

row = 0
for each column col:
    find a row p >= row with matrix[p][col] = 1
    if no p: this variable is free; continue
    swap matrix[p], matrix[row]
    for every other row r with matrix[r][col] = 1:
        matrix[r] = matrix[r] XOR matrix[row]
    row += 1
rank = row

若得到 0 = 1，无解；若相容且秩等于变量数，每个变量被钉死；若秩较小，有自由变量。XOR 域里非零主元永远是 1，不需要除法。

2. 时钟：先让一个周期负责移动

要合并：

$$ x\equiv a\pmod m,\qquad x\equiv b\pmod n, $$

从第一个条件出发，所有候选写成 $x=a+mt$。代入第二个条件，得到：

$$ mt\equiv b-a\pmod n. $$

若 $g=\gcd(m,n)$ 不整除 $b-a$，两只时钟永远错开；若能整除，先除以 $g$，此时 $m/g$ 与 $n/g$ 互质，可用扩展欧几里得找到 $m/g$ 在模 $n/g$ 下的逆元，解出 $t$。

merge(a mod m, b mod n):
    g = gcd(m, n)
    if (b - a) % g != 0: return impossible
    solve t = ((b-a)/g) * inverse(m/g mod n/g) mod (n/g)
    x = a + m * t
    return x mod lcm(m,n), lcm(m,n)

纸上模拟：两次消元、一次合并，都写出收据

先对增广矩阵做两步：R3 ^= R1，再用第 2 行消去第 1、3 行的第 2 列。每步写下矩阵与“为什么解集不变”。然后合并 1 mod 4 与 3 mod 6：

CRT 阶段	式子	得到的信息
参数化	`x=1+4t`
代入第二条件
gcd 兼容性
解出 t
新余数/模数

展开：不要省略兼容性这一行

消元最后得到一条重复行，秩为 2、有一个自由变量。CRT 中 $1+4t≡3\pmod6$，即 $4t≡2\pmod6$；gcd 为 2 且整除 2，约为 $2t≡1\pmod3$，得 $t≡2\pmod3$，最小 $x=9$，新模数 $operatorname{lcm}(4,6)=12$。若兼容性失败，后面“求逆”根本没有许可。

反复合并就得到中国剩余定理（Chinese Remainder Theorem, CRT）的多条件版本。互质只是最常见的简化情况，不是非互质时可以假装不存在的细节。

核心知识：每一步都要保留“解集合”

高斯消元中，一行代表一个约束；合法行变换不增不减满足全部约束的变量赋值。CRT 中，一个同余代表一串等间隔候选；合并后返回的是同时满足两串候选的更稀疏序列。两者都能用“新表达和旧表达等价吗”检查正确性。

XOR 消元若有 $e$ 条方程、$v$ 个变量，朴素复杂度约 $O(ev\min(e,v))$；位集优化可加速整行 XOR。逐步 CRT 的整数乘法可能溢出，模数累乘前要确认题目范围或使用更宽整数。

实现指南

明确数域：实数、模质数、XOR 的“加法/除法”规则不同，不能只换一个 %。
扫描矛盾行时要看系数全 0 且常数非 0；不要仅凭 rank 猜无解。
CRT 合并后把余数规范到 [0, modulus)；负的 % 在 C++ 里需要修正。
求逆前先确认互质；不存在逆元时，先按 gcd 约掉而不是硬做快速幂。

互动小实验室

运行开关与错开的时钟.py。选 x 会显示每次选主元和 XOR 消元后的矩阵；选 c 会逐步合并两组同余，并显示 gcd 兼容性检查。

请先预测预设 CRT 中 $x\equiv1\pmod4, x\equiv3\pmod6$ 的最小非负解，再让程序验算每个余数；再把第二个余数改成 2，看看冲突在哪一步暴露。

扩展与联系

高斯消元会通向解空间、线性基和图的环空间；CRT 会通向周期事件、模方程和状态压缩。二者都只在相应代数结构中正确：模合数下不是每个非零数都有逆元，带负权图也不是线性方程——不要给每个困难问题都套一副代数眼镜。

总结与自检

XOR 消元为什么允许“某一行 XOR 到另一行”？
秩小于变量数且没有矛盾行，为什么会有多解？
CRT 合并中 (b-a) % gcd(m,n) 检查到底比较了什么？

自检答案

对等式两边同时 XOR 同一式不改变真假；至少有一个变量没被独立约束固定；两个余数在共同周期单位上是否一致。

一周预热安排

第 1 天：写三变量 XOR 方程，手动 XOR 两行消掉一个变量。
第 2 天：构造一行 0=1，辨认无解。
第 3 天：在数轴上列出两个小模数的余数序列。
第 4 天：运行互动程序，分别观察秩与 gcd 的作用。
第 5 天：进入高斯消元正式课，再读 CRT 小节。

00-课前零食-开关与错开的时钟.md 11 KB History Raw