XOR 宇宙观察日志-续篇：完美秩序的崩塌
序章：神秘信封
组会结束后，我以为 XOR 宇宙的谜题已经画上了句号。三角形是最稳定的结构。三颗粒子遍历整个相空间。一切简洁、优雅、完满。
直到第二天早上，我在实验室门口发现了一个没有署名的信封。里面只有一张泛黄的纸片，笔迹和石碑上的一模一样：
“连续整数的规律已被破解。但宇宙从来不是整齐的。 若粒子池是任意数组，长度 1500，数值 1500，三元碰撞还能填满相空间吗？ 如果不能，你能数清有多少种结果吗？
我捏着纸片，深吸一口气。转头一看，导师办公室的灯已经亮了，咖啡机的蒸汽正在袅袅升起。
我推开门：“您早就知道有续集，对吧。”
导师头也没抬：“宇宙从来不会只考你一道题。进来吧。”
第一章：有序宇宙的崩塌
“昨天的结论很漂亮，”导师把两页纸并排摊在桌上，“但它有一个前提。”
他指着第一页——那是我们昨天的证明：S = [1, n] 是连续整数。正因为连续，才有从 1 到 M 的完整低位区间，才能用两个数异或出任意 Y，才能用三颗粒子填满整个 2^m 的相空间。
“今天，”他翻到第二页，“前提消失了。”
新的数组不再是 [1, n] 的排列。它可以是任意 1500 个整数，有重复，有空洞，没有连续性。昨天的粒子就像一条完整的街道，从 1 号一路排到 n 号；今天的粒子则是散落在城市各处的 1500 栋建筑，彼此之间没有连贯的编号。
“相空间完备性定律还成立吗？”导师问。
我想了想：“如果没有连续区间，那些‘预组合套餐’就没了。两个数异或不保证能覆盖 [1, M-1] 的全部整数，三元碰撞也就不保证能填满整个相空间。”
“正确。所以今天的问题变了——不再是‘为什么能填满’，而是**‘填不满的时候，到底能填多少个’**。”
第二章：分步合成——当硬算成为唯一的活路
没有公式，没有捷径，只能硬算——“硬算"两个字在脑海里闪过时，我感觉自己昨天写证明时的那股仙气，一瞬间全泄了。“别想那么远，”我拍拍脸，咬开一支新的银河量子能量胶——实习生的咖啡因来源，“先写一个能跑的。”
三元异或的本质是什么？是从集合里挑三个数异或。昨天连续整数时，可以玩一手理论物理，靠基向量和套餐粒子证明“必定填满”；今天任意数组，相空间可能到处都是窟窿，只能老老实实做实验物理，把粒子一颗一颗丢进对撞机里去试。
好在异或有一个好脾气：它满足结合律。也就是说，a ⊕ b ⊕ c 完全可以拆成两步：
- 先建一个“半成品池”：把粒子池里所有可能的两两碰撞结果丢进去。
a ⊕ b的每一种可能都算上。另外，粒子可以重复使用——a ⊕ a = 0，自己撞自己直接湮灭成零，这种白送的产物别忘了也要收进半成品池。 - 再把半成品池里的每个结果，跟原粒子池里的每个粒子再撞一次：
t ⊕ c，得到最终的三元合成产物。
跟合成游戏里的套路一模一样：先拿基础材料两两合成搞出一批半成品，再把半成品和基础材料混合，产出最终道具。简单清晰，毫无黑魔法。
至于数组里可能出现的重复元素？异或只认数值不认位置，多带几个一模一样的数，就像在背包里塞了十几张完全相同的合成配方——除了占负重，没有任何新产出。所以先把原数组压成集合 uniq，去重，轻装上阵。
def uniqueXorTriplets(nums):
uniq = set(nums)
# 两数异或池：所有不同对 + 自己撞自己 = 0
two = {a ^ b for a, b in combinations(uniq, 2)} | {0}
# 三数异或池
three = {t ^ c for t in two for c in uniq}
return len(three)
假设去重后不重复元素个数为 p，两数异或 O(p²)，三数异或 O(p·|two|)。最坏情况下 p ≤ 1500，而数值范围天然给 |two| 戴了紧箍咒——最大值才 1500，所有异或结果都老老实实待在 0 到 2047 之间，|two| 撑死也就 2048。总运算量撑死三百万级别，稳过。
我正准备关掉屏幕去食堂抢饭，忽然盯着“2048”这个数字愣住了。
2048，2^11。比最大值 1500 大的最小 2 的幂——这个数字我昨天见过。我在白板上画过它，在线性代数里证过它，用 1 << n.bit_length() 当着一屋子人的面板书过它。
在 XOR 宇宙里，连续整数 [1, n] 的相空间大小就是 M = 2^m，所有异或结果被牢牢锁在 [0, M-1] 这个区间里——这是 XOR 宇宙最底层的骨架。今天虽然数组不再连续，但这个结论仍然成立——只是填不满罢了。
既然相空间天然就是一个从 0 到 M-1 的连续整数区间，为什么不直接把相空间铺成一张布尔表呢？
第三章：布尔数组——给相空间画一张方格纸
想法很简单：用一个长度为 M = 1 << max_val.bit_length() 的布尔数组来代替集合。
数组的索引从 0 到 M-1，天然就是异或值，不需要哈希，不需要冲突处理。每一个格子都是相空间里的一枚坐标。arr[x] = True 就代表“x这个粒子被合成出来了”。昨天，数组每一格都是True；今天，有的能变True，有的不能——而我的工作，就是数清楚有多少格变成了 True。
实现起来，不过就是上面解法的底层直译：把集合换成布尔数组，把哈希查找换成数组下标。循环还是那些循环，只是常数被压低了，相空间的结构清清楚楚地摊在眼前。
def uniqueXorTriplets(nums):
uniq = list(set(nums))
max_val = max(uniq)
M = 1 << max_val.bit_length()
# 两数异或池（布尔数组版）
two = [False] * M
two[0] = True # a ⊕ a = 0
p = len(uniq)
for i in range(p):
a = uniq[i]
for j in range(i + 1, p):
two[a ^ uniq[j]] = True
# 三数异或池（布尔数组版）
three = [False] * M
for t in range(M):
if two[t]:
for c in uniq:
three[t ^ c] = True
return sum(three)
尾声：真实的宇宙
两种写法提交上去，runtime 差了大约一半。布尔数组更快，但说实话，它只是常数优化。真正让我觉得有意思的，不是快了那零点几秒，而是这两天任务的那种奇妙对称感。
昨天的宇宙是完美的：连续整数提供了完整的低位图案，三颗粒子能填满整个相空间，每一个格子都被点亮。所以你不需要真的去数——数学告诉你是 2^m。
今天的宇宙是任意的：数组里有空洞，有跳跃，有缺失。三元碰撞可能填不满整个相空间，有些格子永远是暗的。所以你只能只能一颗一颗粒子扔进对撞机，一格一格数过去——遍历是唯一的出路。
宇宙的底层规则并没有变：M = 2^m 的边界没有变，异或运算的结合律没有变，a ⊕ a = 0 的湮灭法则没有变。
变的只有你的处境：昨天你站在秩序的中心，一支粉笔、两页线性代数，就能预言一切；今天你被丢进了一团混沌，只能拿着布尔数组，一颗一颗地摸索。
我关掉屏幕，窗外 XOR 宇宙的星空依旧静谧。
或许，连续整数是 XOR 宇宙的童话版本。任意数组才是真实世界。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。