企业官网建设流程全解析

翻到 UVa 13081 的时候，题面的具体数字我已经记不清了，但XOR Sequence Revisited这个标题让我停了几秒。异或、序列、再探，三个词叠在一起，基本已经预告了这类题的标准命运：不能真的把序列跑完。Revisited这后缀尤其关键——它说明旧模型已经被人玩过了，这次是换一层的考法，旧的暴力思路必须升级。

这篇文章我不打算去复原那一份题面，而是把这一类“生成规则已知、查询区间异或和”的问题从头到尾推一遍。连续整数异或、带状态递推生成、周期压缩、前缀异或翻车点，这些会全部走一遍。适合刚接触异或相关题的读者，也适合那些被同类题卡过、想补一套稳定打法的人。

1. 区间异或查询的万能翻译：先做前缀异或

1.1 为什么异或也能“相减”

看到“区间查询”四个字，第一反应应该是前缀数组，这套思路对加法、乘法、异或都成立，只是异或的特殊之处在于：它自己就是自己的逆运算。

加法的逆运算是减法，所以sum(L,R) = pref[R] - pref[L-1]。乘法的逆运算是除法，所以mul(L,R) = pref[R] / pref[L-1]。异或呢？a ^ a = 0，a ^ 0 = a，所以xor(L,R) = pref[R] ^ pref[L-1]。

这个公式看起来平平无奇，但它把一次 O(区间长度) 的求和压成了 O(1)。更关键的是，后续所有高级做法都是在为“能快速求出任意前缀异或”服务。

举个例子。假设序列是：

a = [3, 5, 7, 9, 11]

前缀异或数组pref[i]表示a[0] ^ a[1] ^ ... ^ a[i]：

想求a[1] ^ a[2] ^ a[3]，也就是5 ^ 7 ^ 9，直接算pref[3] ^ pref[0] = 8 ^ 3 = 11，而5 ^ 7 ^ 9 = 11，一致。

原理也很直觉：pref[R]里装着a[0] ~ a[R]的异或，pref[L-1]里装着a[0] ~ a[L-1]的异或。两者异或时，前L个元素各自出现了两次，全部抵消，留下的刚好是a[L] ~ a[R]。

这个转化虽然简单，但是几乎所有“区间异或”问题的地基。后面的连续整数异或、生成序列异或，本质都在解决同一个问题：能不能用 O(1) 算出某个位置的pref[i]。

1.2 下标对齐：错一个就全错

前缀异或公式最容易踩的坑是下标。假设序列下标从 0 开始，查询闭区间[L, R]，答案一定是：

ans = pref[R] ^ pref[L-1]

注意是L-1不是L。如果写成pref[R] ^ pref[L]，那么a[L]左边的东西虽然被消掉了，但a[L]本身会被多消一次，结果里就莫名其妙少了一个元素。

下标从 1 开始的情况也一样，只是要把题目的l, r整体减一映射到内部下标。我见过不少人公式背得滚瓜烂熟，但遇到 1-indexed 的输入，忘了减一，WA 到怀疑人生。

还有一种边界：L = 0时，L - 1 = -1。不要试图访问pref[-1]，直接规定pref[-1] = 0即可。因为“一个元素都没有”的异或和就是0，这正好不改变结果。

这里顺手提醒一句：如果查询要求的是区间内“去重后的异或和”，那前缀法就不能直接用了，因为同一个数字可能出现多次，异或会抵消。那种情况需要离线加可持久化之类的操作，已经超出了这套基础框架。我们这篇文章讨论的范围，是普通的多重集合区间异或，对应大量生成序列题的主战场。

2. 连续整数异或的 4 周期配方

2.1 打表：先看小数据再谈公式

最常见的 XOR 序列题，其实是连续整数本身：求L ^ (L+1) ^ ... ^ R。看起来没有任何“生成规则”，但它仍然有漂亮的封闭解。

定义：

g(n) = 0 ^ 1 ^ 2 ^ ... ^ n

先别急着推公式，从 0 开始打一张小表：

数据一摆出来，模式已经非常明显：

这就是那个经典的四分支结论：

unsigned xor_0_to_n(unsigned n) { switch (n & 3) { case 0: return n; case 1: return 1; case 2: return n + 1; default: return 0; } }

n & 3就是n % 4。这里我习惯写成位运算，因为这类题的数据量一旦变大，取模代价虽然不大，但位运算的语义更直接。

区间查询自然变成：

unsigned xor_l_r(unsigned l, unsigned r) { return xor_0_to_n(r) ^ xor_0_to_n(l - 1); }

l = 0时手动返回1ULL ^ 2ULL ^ ... ^ r即可，当然也可以直接套公式：xor_0_to_n(-1)返回 0，前提是你对外层做了保护。

2.2 为什么是 4，不是 2 或 8

打表被一些人看成“投机取巧”，但在异或题里，打表观测出的规律往往直接暴露了底层结构。

连续整数异或为什么以 4 为周期？看一组四个数：

4k ^ (4k+1) ^ (4k+2) ^ (4k+3)

这四个数二进制低两位分别是00, 01, 10, 11，异或后低两位是00。而它们的高位，除了低两位以外，其他位完全相同。相同的高位异或偶数次，结果也是 0。所以：

4k ^ (4k+1) ^ (4k+2) ^ (4k+3) = 0

这就是“每四个连续整数互相抵消”的原因。既然整组归零，那么g(n)就只取决于最后没凑成整组的余数，也就是n mod 4。

还有一个按位拆的视角：异或第j位时，只关心该位 1 的个数是奇数还是偶数。从0数到n，第j位会在长度2^(j+1)的窗口内出现2^j个 1。这个结构在不同位上自动形成错位，最终共同决定了上面那个四分支。

不管用哪种解释，结论都是一样的：连续整数异或的复杂度是 O(1)，根本不依赖区间长度。

2.3 公式之外的三个延伸

这个四分支公式本身不难，但我建议把它当成一种思维模板来记，因为它能延伸到三类更复杂的场景。

第一，如果序列是某个排列的“伪连续”形态，先尝试把它拆成“连续整数段加上常量”。比如a[i] = i ^ C，因为C只在某些位上翻转，可以逐位统计，或者根据区间长度奇偶来调整结果。

第二，如果一个序列刚好在某个有限域上遍历“全部取值”，那整圈异或往往可以直接由公式算出。比如0 ^ 1 ^ ... ^ (2^K - 1)，当K >= 2时结果是 0。这个性质后面在生成序列里会用到，特别省事。

第三，打表找周期这件事，不要只在小数据里做，把它写成一个工具的辅助函数，直接在程序里动态找周期，这才是竞赛里真正能救命的那招。下一节我会用 xorshift16 把这个过程完整跑一遍。

3. 生成型序列：用 xorshift16 跑通周期扣账

3.1 问题模型：一个“异或移位”生成的序列

现在把问题升级。假如序列不是连续整数，而是由一个递推生成器逐项产出，每次查询还是区间的异或和。这是XOR Sequence这类题更常见的形态。

我选一个很有代表性的生成器：16 位 xorshift。它每一步只做三件事：

uint16_t xorshift16(uint16_t x) { x ^= x << 7; x ^= x >> 9; x ^= x << 8; return x; }

每一步都只用了异或和移位，所以它生成的序列确实是“XOR sequence”。这种生成器看起来有点随机，但它有一个致命的约束：状态是 16 位，最多只有 65536 种不同状态。

一旦状态重复，整个后续序列就会完全复刻之前已经走过的轨迹。这是有限状态自动机的铁律。

这么说吧，只要生成规则确定、状态空间有限，序列最终一定进入周期。差别只是周期从哪开始、长度是多少。我们要做的，就是把这个周期找出来，然后用它压缩查询。

3.2 找周期：自动检测 cycleStart 和 cycleLen

找周期的标准写法是：记录每个状态第一次出现的下标。当某个状态第二次出现时，第一次出现的位置就是循环起点，当前下标减去循环起点就是周期长度。

下面是通用实现：

vector<uint16_t> buildCycle(uint16_t seed) { vector<int> where(1 << 16, -1); vector<uint16_t> seq; uint16_t s = seed; int idx = 0; while (where[s] == -1) { where[s] = idx++; seq.push_back(s); s = xorshift16(s); } int cycleStart = where[s]; int cycleLen = (int)seq.size() - cycleStart; printf("cycleStart = %d, cycleLen = %d\n", cycleStart, cycleLen); return seq; }

注意这里用where数组而不是简单拿s == seed判断循环。为什么？

因为某些递推不是双射，状态可以“合并”。比如从seed出发可能先走一段不重复的前缀，然后才掉进某个环。这种情况下s永远不会再次等于seed，但环是真实存在的。记录firstSeen才是一劳永逸的做法。

很多人一上来默认周期必须从第 0 项开始，结果遇到有 preperiod 的生成器，查询全部错位。这个细节我会在第五章再拎出来强调一次。

回到 xorshift16。用上面代码跑一遍，状态空间上限只有 65536，所以最多枚举 65536 次。即便生成器的多项式性质不理想，也不会出现“找周期把程序跑死”的情况。

找到周期后，我们要把序列的前缀异或数组建出来。注意这个前缀数组只需要覆盖到seq.size() - 1，不需要覆盖到题目给的最大下标。剩下的部分全用周期压缩。

vector<uint16_t> seq = buildCycle(seed); vector<unsigned> pref(seq.size()); unsigned cur = 0; for (int i = 0; i < (int)seq.size(); ++i) { cur ^= seq[i]; pref[i] = cur; } int cycleStart = /* 上述函数计算出的值 */; int cycleLen = /* 上述函数计算出的值 */; unsigned headXor = (cycleStart > 0 ? pref[cycleStart - 1] : 0); unsigned cycleXor = pref[seq.size() - 1] ^ headXor;

这里cycleXor是“完整一圈”的异或值。如果完整一圈长度是cycleLen，那连续重复若干圈的异或结果就很好处理：重复偶数圈抵消成 0，重复奇数圈等价于一圈。

3.3 从周期到前缀异或：两次取模解决一切

现在设计solve(n)，表示求a[0] ^ a[1] ^ ... ^ a[n]。

分成三段：

1. 最前面的“小尾巴”：n < cycleStart时，直接返回pref[n]。
2. 如果n >= cycleStart，那么循环部分的总项数是n - cycleStart + 1。
3. 把循环部分的总项数拆成full * cycleLen + rem，其中full是完整循环圈数，rem是最后剩余的一小段。

unsigned long long xorPrefix(long long n) { if (n < 0) return 0; if (n < cycleStart) return pref[n]; unsigned long long cnt = (unsigned long long)n - cycleStart + 1; unsigned long long full = cnt / cycleLen; int rem = (int)(cnt % cycleLen); unsigned ans = headXor; if (full & 1) ans ^= cycleXor; if (rem > 0) { ans ^= pref[cycleStart + rem - 1] ^ headXor; } return ans; } unsigned xorQuery(long long l, long long r) { return xorPrefix(r) ^ xorPrefix(l - 1); }

关键点在于cycleStart == 0时headXor = 0，公式自动退化成常见的纯周期版本。cycleStart > 0时，那段小尾巴单独算一次，然后跟循环部分拼起来。

复杂度：

• 找周期：O(T)，T 是实际周期长度，上限是状态空间大小。
• 预处理：O(T)。
• 单次查询：O(1)。

对一道“生成规则简单、查询次数很多”的题来说，这个复杂度已经接近最优。你不需要把10^18的序列跑完，只需要把有限状态里的环找出来就行。

3.4 一个整圈异或为 0 的黄金验证

如果你的生成器恰好是最大长度的 xorshift16，那么它的循环节长度会是 65535，并且会遍历1 ~ 65535的所有非零 16 位整数。

这时有一个很舒服的性质：一个完整循环的异或值等于：

1 ^ 2 ^ 3 ^ ... ^ 65535

而0 ^ 1 ^ ... ^ 65535 = 0（因为 16 位整数全集，每一位上的 1 都出现偶数次），所以：

1 ^ 2 ^ ... ^ 65535 = 0

整圈异或直接是 0。这意味着full那一项无论奇偶都不用管，答案只由headXor和最后的rem段决定。

我有段时间特别喜欢用这个特性做程序自检：跑出来的cycleXor如果不是 0，那很可能是找周期时数组下标写错了，或者递推公式没截断到位。一个反直觉却有数学保证的常数，往往比十组随机对拍更能暴露问题。

不过这只是一个“锦上添花”的验证。真正的工程保障，还是得靠最后那节对拍。

4. 实战翻车记录：四个很小但毁全题的细节

4.1 cycleStart 不是 0 的隐藏小尾巴

很多人写周期相关代码，总默认周期从序列开头就开始。一旦遇到递推不是双射、状态从seed要先滑一段才进入环里的情况，所有下标都会整体偏移。

解决方式就是前面代码里的where数组。不要用s == seed判断周期，而是等某个状态第二次出现。这样无论循环起点在哪，solve都能正确处理。

我自己的经验是：写生成器时顺便加一个断言，确认cycleStart + cycleLen == seq.size()。如果不等，说明找周期的循环本身写错了。这个断言帮我抓过好几次数组越界的低级错误。

4.2 L-1 变负数：边界永远单独写

xorQuery(l, r)内部调用xorPrefix(l - 1)，一旦l是 0，l - 1变成 -1。如果函数参数是无符号类型，这个 -1 会变成一个巨大正数，然后被当成n用周期公式处理，结果完全不可控。

所以两个习惯：

1. xorPrefix的参数要么用有符号long long，要么在函数开头处理n < 0。
2. 查询函数的l和r如果是题目给的uint64_t，转成有符号时也要小心，最好在外部统一转好。

这个坑看起来弱智，但真到高压赛场上很容易写崩，因为本地小数据测试很可能查不到l = 0这种边界。

4.3 用异或当加法：前缀和公式的误写

我见过不少人在纸上推导得很顺，写着写着就把公式写成了：

pref[R] - pref[L-1]

或者：

pref[R] + pref[L-1]

这两种统统不对。异或的世界里没有“减法”，只有“自己抵消自己”。

正确的写法永远是：

pref[R] ^ pref[L-1]

如果你担心自己记混，可以这么想：pref[R]里包含目标区间右侧所有元素，pref[L-1]里包含目标区间左侧所有元素。两者异或时，中间重叠的部分抵消，留下来的就是从L到R的结果。这个“重叠抵消”的模型比“相减”更接近本质。

4.4 对拍：用暴力验证公式，而不是相信推导

公式推导得再漂亮，我也建议写一个暴力函数做对拍。尤其是生成型序列，状态数量不多的时候，暴力直接循环就完事：

uint16_t brute(long long l, long long r) { uint16_t s = seed; // 先跳到 l，这一步只用于小范围对拍 for (long long i = 0; i < l; ++i) s = xorshift16(s); uint16_t ans = 0; for (long long i = l; i <= r; ++i) { ans ^= s; s = xorshift16(s); } return ans; }

然后随机生成几百组l, r，把brute和xorQuery的结果比对。只要有一次不一致，就把那组l, r单独拎出来断点调试。

我在实际处理这类题时，从来不会省掉这一步。倒不是不相信公式，而是公式的“正确”和“代码实现的正确”之间存在巨大鸿沟。周期起点缩进一格、数组下标差一、某个中间变量被意外截断成 16 位，都会让结果从第 1000 个查询开始全面爆炸。对拍能把这些隐性错误全部炸出来。

还有一个很实用的小技巧：对拍时故意让l或r落在cycleStart - 1、cycleStart、cycleStart + cycleLen这些临界点附近。因为周期边界是错误高发区，普通随机数据很难扎到这些点上，手动补几组边界用例，能省很多排查时间。