leetcode3513 XOR 宇宙观察日志：三颗粒子如何征服整个相空间

XOR 宇宙观察日志：三颗粒子如何征服整个相空间

序章：来自 X-3513 星系的考古发现

在遥远的 XOR 宇宙，物理规律与我们熟知的世界截然不同。那里的基本粒子不是夸克，而是整数。它们之间的作用力只有一种——异或碰撞。两颗粒子撞在一起，会瞬间融合成一颗全新的粒子，新粒子的数值恰好等于两颗原粒子按位异或的结果。用地球代码写出来，就是 a ⊕ b。

XOR 宇宙的考古学家最近挖到了一块古老石碑，上面刻着 XOR 宇宙的终极谜题：

当 n 个连续整数粒子 [1, 2, …, n] 排列成阵，从中任选三颗（允许重复），让它们异或碰撞，最终能诞生多少种不同的粒子？

石碑上没有答案。为了一探究竟，银河系科学院派出了最廉价的劳动力——实习观察员，也就是我，去实地考察。

第一章：田野调查——从暴力枚举到惊人的规律

导师的指示很直接：“先把问题本身搞清楚。写个暴力程序，从小 n 开始跑数据。数据不会撒谎。” 于是我写了个朴素的三重循环：

def uniqueXorTriplets(nums: List[int]) -> int:
    results = set()
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                results.add(a ^ b ^ c)
    return len(results)

粒子对撞机的输出很快铺满了我的屏幕：

n	粒子池	不同结果数
1	[1]	1
2	[1,2]	2
3	[1,2,3]	4
4	[1,2,3,4]	8
5	[1,2,3,4,5]	8
6	[1..6]	8
7	[1..7]	8
8	[1..8]	16
9	[1..9]	16
…	…	…
15	[1..15]	16
16	[1..16]	32

规律像夜空里的星座一样，从数据里慢慢浮现出来：只要 n ≥ 3，结果数永远是 2 的幂，而且幂次恰好等于 n 的二进制位数。 记这个位数为 m，结果数就是 2^m。

我盯着这行结论发了好一会儿呆。 2^m ——所有 m 位二进制数加在一起也是这么多，从全 0 到全 1，一个不多，一个不少。换句话说，只要 n≥3，三颗粒子一通乱撞，居然就能一个不漏地变出从 0 到 2m−12m−1 的所有整数！

“也就是说，给你一小袋连续编号的粒子，你拿三颗撞一撞，就能造出这片宇宙里理论上能存在的所有粒子？”我忍不住自言自语。

“总结得不错。”导师不知道什么时候飘到了我身后，“你刚刚撞出来的，是 XOR 宇宙的一条基本定律——三粒子异或碰撞能遍历整个 m 位二进制空间。”

他顿了顿，补上致命一问：“现在告诉我，为什么偏偏是三个，不是两个，也不是四个？”

我沉默片刻：“……我能用 ChatGPT 吗？”

导师呷了一口咖啡，慈祥地笑了：“不能。”

“那我能用——”

“线性代数。”他把一本积灰的《线性代数学》拍在我面前，“明天组会，我希望你嘴里吐出来的不是 prompt，是证明。”

我：“……”

第二章：理论突破——XOR宇宙的数学底色

我不得不翻开那本积灰的《线性代数学》，在翻到第 666 页时，我看到了一个似曾相识的名词：GF(2) 域上的向量空间。旁边还有我当年留下的潦草笔记——把每个整数写成二进制，异或就是逐位的不进位加法。比如：

5 = 0b101 = 向量 (1, 0, 1)
3 = 0b011 = 向量 (0, 1, 1)
5 ⊕ 3 = 0b110 = 向量 (1, 1, 0)

这等价于逐位做“1+1=0”的模2加法：
(1,0,1) + (0,1,1) = (1,1,0)

每一位就像一个独立的小开关，两个 1 相遇变成 0，就像灯的开关——按一次亮，再按一次灭。所有 m 位二进制数排在一起，就构成了一个 m 维的向量空间——数学上叫做 GF(2)^m。它恰好包含 2^m 个向量，从 0 到 2^m-1，一个不多，一个不少。

这正是导师口中的“相空间”——GF(2)^m 是学名，“相空间”是它在 XOR 宇宙里的物理外号。它就是XOR宇宙中一切可能粒子的总目录，容量刚好 2^m。

现在回看我们的粒子库 S = {1, 2, …, n}，它恰好卡在一个微妙的位置上：设 m 是 n 的二进制位数（满足 2^{m-1} ≤ n < 2^m），那么 S 天然包含两个重要组成部分：

1. 基向量——生成一切的"原子粒子"

在 m 维空间里，需要 m 个互相独立的“基”才能搭出一切。S 中恰好包含 1, 2, 4, 8, …, 2^{m−1} 这些 2 的幂，因为最大的那个 M = 2^{m−1} 不超过 n，所以全都在手。它们的二进制只在某一个比特位上是 1，其余全是 0，是最标准不过的正交基。

1  = 0b00001 ← 只有第0位是1
2  = 0b00010 ← 只有第1位是1
4  = 0b00100 ← 只有第2位是1
8  = 0b01000 ← 只有第3位是1
......

有了这些基，理论上你可以通过不限次数的异或，拼出相空间里的任何向量。比如 13 = 8 ⊕ 4 ⊕ 1。

2. 连续整数——预组合的"套餐粒子"

但光有基向量还不够——如果 S 里只有孤零零的 {1,2,4,8,…}，想造个复杂点的数，大概率要异或很多次才能得到。好在 S 是一段完整的连续整数集合，这意味着我们不仅有"原子粒子"，还有各种预先组装好的"套餐粒子"。

比如当 n = 5 时，S = {1, 2, 3, 4, 5}，其中：
1, 2, 4 是基向量（原子粒子）
3 = 0b011 = 1 ⊕ 2（组合好的"1+2套餐粒子"）
5 = 0b101 = 1 ⊕ 4（组合好的"1+4套餐粒子"）

这些套餐粒子像是预制菜，把原本需要多次异或才能调出的低位图案，提前打包进了一个数里。有了它们，我们可以用一个套餐顶替两三个基的组合，省下反复组装的麻烦。

至此，材料已经齐全：原子粒子负责提供所有维度上的独立控制，套餐粒子提供现成的低位组合。接下来的问题就是——为什么只要三个粒子异或，就能精确地刷出整个 2^m 大小的相空间？

第三章：三元 XOR——恰到好处的"自由度"

原子粒子给了我们独立操控每一个比特位的能力，套餐粒子给了我们现成的低位组合，接下来要回答的是：为什么恰好三个粒子的异或，就能刷出整个相空间？

答案藏在一条不起眼的规则里：粒子可以重复使用。正是因为允许重复，三粒子碰撞其实能变出三种花样：

单包直出：a ⊕ a ⊕ a = a，效果等同于直接取出粒子 a。
用完就扔：a ⊕ a ⊕ b = b，前两个 a 互相抵消，只剩下 b。
真正混合：a ⊕ b ⊕ c，用三个不同的粒子去合成新的向量。

依靠这三招，我们可以用一套流水线，把 0 到 2^m−1 之间的任意一个目标数 T 造出来。

T = 0：用“真正混合”招式：1 ⊕ 2 ⊕ 3 = 0（只要 n≥3，1,2,3 都在库房里，随手就来）。
1 ≤ T ≤ n：T 本身就是库房里的合法粒子，用“用完就扔”：T ⊕ 1 ⊕ 1 = T，或“单包直出”：T ⊕ T ⊕ T = T，怎么玩都行。
n < T ≤ 2^m - 1：此时 T 超出了粒子库的最大编号，但还在相空间内，最高位必定是 1。这时，我们可以先搬出那个最大的“原子粒子”——M = 2^{m-1}，它的二进制是 100…0，是一个只控制最高位的大开关（ M ≤ n，它在我们粒子库S中）。接着，就可以把 T 拆成 顶层开关 M ⊕ 底层图案 Y：令 Y = T ⊕ M。M 恰好按灭了 T 的最高位，所以 Y 的最高位变成 0，也就是说 Y 严格小于 M——Y 要么是 0，要么就藏在 1 到 M-1 的某处。
- 如果 Y = 0（即 T = M）：直接用“用完就扔” M ⊕ 1 ⊕ 1 = M，M 和 1 都在粒子库S 中。
- 如果 Y > 0：我们需要再找两个库房里的粒子 a 和 b，让 a ⊕ b = Y。怎么找？
  - 找到 Y 二进制里最左边的那个“1”位，也就是最高位，记为 a。
  - 如果 Y 不是 2 的幂，选 b = a ⊕ Y。因为 a 和 Y 的最高位相同，异或之后 b 的位数比 a 小，于是 a 和 b 都落在 1 到 M−1 之间，也就都在粒子库 S 中。如果 Y 是 2 的幂，微调一下，改用 a’ = a + 1，b = (a + 1) ⊕ Y，因为 a < M，a+1 ≤ M 所以还是在粒子库范围内，而 b 变成一个更小的非零数，两者都属于 S。
无论哪种情况，我们都能在 S 里找到两个合法的粒子 a 和 b，满足 a ⊕ b = Y。最后一步，把“顶层开关”M 和这对低位拼块一起投入对撞机：M ⊕ a ⊕ b = M ⊕ Y = T。恰好三次碰撞，目标粒子 T 诞生。

所以，对任意 T ∈ [0, 2^m-1]，我们都能用三颗粒子异或碰撞把它造出来。三元碰撞的结果集恰恰是整个 m 维相空间，不同的 T 不多不少，正好 2^m 个。在代码里，这个值就是1 << n.bit_length()

def uniqueXorTriplets(nums: List[int]) -> int:
    n = len(nums)
    return n if n < 3 else 1 << n.bit_length()

第四章：两个粒子的残局，以及第四颗粒子的徒劳

“既然 Y 用两个粒子就能拼出来，那省掉 M，直接用二元 XOR 不也能行？”

答案是：拼得出局部，拼不出全局。

回到我们的实验数据。拿 n=4 做个两两异或，结果集是这样的： {0,1,2,3,5,6,7}，唯独永远缺少 4。为什么偏偏是 4？把 4 写成二进制：100。最高位亮着，下面两层全灭。要想用两个 1~4 之间的数异或出这个图案，你必须让最高位变成 1，同时低两位干净地归零。可问题来了：

最高位是 1 的数只有 4，用它去异或最高位是 0 的数（1,2,3），低两位会被那个小数搅乱；
异或另一个最高位也是 1 的数（4 自己），最高位倒是因 1⊕1=0 而灭了，但结果变成了 0。左右为难，横竖得不到那个漂亮的 100。

用空间几何的话说，两颗粒子缺少独立操控最高位的能力。

二元异或 S+S 只能在低位灵活腾挪，一碰到最高位就捉襟见肘，相空间里永远残留几个“幽灵数”，像一张拼图永远缺了正中间那一块。第三颗粒子 M 正是一把独立的高位开关，把它加进来，原本只能覆盖 [0, M−1] 的二元组合，被平移到了 [M, 2^m−1] 的高地。两片拼接，整个相空间才第一次严丝合缝地闭合。

“既然三颗粒子已经能点亮所有 2^m 种情况，那再扔进第四颗粒子会发生什么？”

答案是：无事发生。四元碰撞 a⊕b⊕c⊕d 可以看成 (a⊕b⊕c) ⊕ d。括号里的三元组早已能跑遍整个相空间，再异或一个 d，只不过是把整张地图在手里翻转了一遍——所有能去的地方你早就去过了。就像解锁了全地图之后，再买一个 DLC 也只换皮肤不扩边界。

所以石碑上的预言精确地指向“三”，而不是二或四。两颗太少，四颗浪费，三颗恰好是打通相空间任督二脉的临界之数。

尾声：XOR宇宙的终极浪漫

组会那天，我在白板上写完最后一页证明，转过身，发现导师难得地没有打断我。

“所以，XOR 宇宙用极度吝啬的粒子种类，演绎了最慷慨的生成法则。只要三颗粒子，就能造出整个相空间。两颗不够，因为缺一把独立的高位开关；四颗多余，因为地图已经被三元组跑遍了。”

导师沉默了一会儿，“一颗粒子只能是自己，”他缓缓开口，“两颗粒子开始产生关联，三颗粒子——刚好够你触达一切。” 他在实习报告上批了一个巨大的 “A”，又在旁边画了一个小小的三角形。然后放下笔，看了我一眼：“现在你明白，为什么三角形是最稳定的结构了？”

我关掉实验日志，投影仪的光芒渐渐暗下去。而窗外，XOR 宇宙的星空静谧如谜。

本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。