拆位法+期望线性性：求解随机区间位运算期望的完整推导

我到现在还记得第一次在题目列表里看见“P10500 Rainbow的信号”时的感受：“期望”和“位运算”放在一起，旁边还挂着“普及+”，第一反应是这题怕不是要搞什么高深概率论。但实际做下来，它反而是我见过最适合用来理解拆位法和期望线性性的题目之一。题目本身不绕：给一个长度为 n 的整数序列，等概率随机选一组 l ≤ r，把区间 [l, r] 的按位与、按位或、按位异或都作为“信号值”，最后求这三个随机变量的数学期望。想通拆位法之后，这道题就是 30 次 O(n) 扫描的事。这篇文章我把完整的推导链、计数方法和代码一并写出来，适合刚接触期望类算法题、或者会写暴力但不知道怎么优化的读者。

1. 先看懂题目在算什么东西：随机区间和三种位运算

1.1 期望不是洪水猛兽，等概率场景下就是“全样本平均”

很多同学看到“期望”两个字就开始慌，其实这题的期望定义非常朴素。随机试验是：从所有满足 1 ≤ l ≤ r ≤ n 的区间中等概率选一个，总区间数显然是

total = n(n+1)/2

每个区间被选中的概率都是 1/total。那么某个信号值 X（比如按位与的结果）的期望就是

E[X] = Σ X(区间) × (1/total) = (所有区间的信号值之和) / total

这一步不涉及任何条件概率、递推、生成函数，纯粹是把定义翻译成求和问题。热词里出现的记号 e{·} 就是对括号内随机变量取数学期望，在这个模型下它就是“所有可能取值的加权平均”。

所以核心目标变成了：快速求出所有子区间的 AND 之和、OR 之和、XOR 之和。如果 n 只有 100，直接三层循环枚举区间就行了。但 n 到 1e5 甚至更大时，O(n²) 个区间根本枚举不完，必须要找批量统计的办法。

1.2 为什么不能直接枚举区间，以及位运算带来的突破口

暴力做法的复杂度是 O(n²) 甚至 O(n³)。n = 1e5 时，区间数量大约 5e9，这是不可接受的。但注意一个关键事实：这题里所有运算都是位运算，结果只跟每个数拆成二进制之后每一位上的 0/1 有关。

数值本身可以拆成二进制权值的和：

x = Σ (bit_k(x) × 2^k)

这里 bit_k(x) 表示 x 的第 k 个二进制位。位运算有个非常友好的性质：AND、OR、XOR 在每一位上的结果，只取决于参与运算的数在这一位上的取值，不会跨位干扰。于是“整个区间的位运算结果”可以按位拆开：

value(区间) = Σ (第 k 位上的运算结果) × 2^k

求所有区间 value 的总和，等价于对每个二进制位 k，先统计“该位在所有区间上的运算结果为 1 的区间数量”，再乘上权重 2^k 累加。这就是拆位法的核心思想。

也许你会问：这样子做有什么好处？好处在于，把任意大整数的问题，变成了 30 个（int 范围内）或者 60 个（long long 范围内）的 01 串统计问题。01 串的连续区间性质非常清晰，可以设计 O(n) 的扫描算法。这比直接面对大整数区间要容易太多。

1.3 三个“随机变量”在这个模型里可以同时求

题目要的是三个期望：按位与、按位或、按位异或。拆位之后，对某一位 k，问题都变成了一个 01 数组上的统计：

• 区间按位与的结果在这一位为 1，等价于区间内所有数这一位全为 1；
• 区间按位或的结果在这一位为 1，等价于区间内至少有一个数的这一位为 1；
• 区间按位异或的结果在这一位为 1，等价于区间内这一位为 1 的个数是奇数。

下一个问题就非常具体了：给定一个长度 n 的 01 串，如何分别统计“全 1 区间数”“含 1 区间数”“1 的个数为奇数的区间数”？这三个统计各自都有基于扫描的线性解法，下面一节详细拆开讲。

2. 拆位法是这类题的默认起手式：位独立性 + 期望线性性

2.1 “期望求和可以拆开”是数学上最关键的通行证

很多同学会问：就算把每个数拆成二进制位，那每个区间的结果不还是 30 个位的结果乘以 2^k 再加起来吗？这样拆开统计真的合法吗？答案是合法的，因为期望有线性性质，不要求各部分独立：

E[X + Y] = E[X] + E[Y]

这里 X 可以理解成“某一位贡献的部分结果”，Y 是另一位贡献的部分结果。它们之间可以有相关性，线性性依然成立。所以我们可以非常放心地逐位计算、逐位累加，既不需要知道区间分布，也不需要处理位与位之间的相关性。

这一条几乎是所有“位运算 + 期望/总和”题的通用钥匙。很多看起来带随机性的题，最后都会被这条性质拆成若干个确定性的计数问题。

2.2 位运算在某一位置上的语义：三种运算退化成三类区间条件

拆到某一位之后，原来的整数序列变成了 01 序列。原本复杂的三种位运算，在这一位上退化成非常直观的逻辑判断：

这三句话是整个算法的核心。后面所有计数推导，都只是这三个条件的组合数学应用。

2.3 一个生活化的类比：一排灯泡的状态

为了帮助理解，可以想象一排灯泡，亮表示 1，灭表示 0。

• AND 为该位为 1，等价于“这一段灯泡从 l 到 r 全亮”；
• OR 为该位为 1，等价于“这一段至少有一盏亮灯”；
• XOR 为该位为 1，等价于“这一段亮灯数量是奇数”。

统计一段路灯“全亮”“至少一亮”“亮数为奇数”显然是三种不同的问题，但它们都能通过维护“最近状态位置”或者“前缀状态计数”来线性求解。这也是这类题最有趣的地方：看起来三个统计要三个不同算法，实际上只是在同一次扫描中各自维护一个变量。

3. 逐位扫描的三个计数核心：AND 看最近 0、OR 看最近 1、XOR 看前缀异或状态

3.1 AND：维护最近一个 0 的位置 last0

先看最直观的“全 1 区间”统计。枚举右端点 i，考虑所有以 i 结尾的区间 [l, i]，希望区间内全部是 1。

如果某个位置 pos 是 0，那么任何左端点 l ≤ pos 的区间都会包含这个 0，导致 AND 为 0。因此，合法的左端点 l 必须严格大于“i 左边最近的一个 0 的位置”。设这个最近 0 的位置为 last0，那么以 i 结尾的全 1 区间数量就是 i - last0。

举个例子：01 串为 1, 0, 1, 1。

• i = 1，bit = 1，last0 = 0，贡献 1，对应区间 [1,1]；
• i = 2，bit = 0，更新 last0 = 2，贡献 0；
• i = 3，bit = 1，last0 = 2，贡献 1，对应区间 [3,3]；
• i = 4，bit = 1，last0 = 2，贡献 2，对应区间 [3,4] 和 [4,4]。

累计 1 + 0 + 1 + 2 = 4。你手动把所有子区间列出来验证，全 1 的确实是 [1,1]、[3,3]、[3,4]、[4,4] 这 4 个，完全吻合。

这个统计的本质是：右端点固定时，满足条件的左端点构成一个连续后缀。因为全 1 条件对左端点有单调性——左端点越靠右，区间越短，越不可能包含 0。

3.2 OR：维护最近一个 1 的位置 last1

再来看“至少一个 1”的区间统计。同样枚举右端点 i，对于区间 [l, i]，只要 l 不超过 i 左边最近的 1 的位置 last1，这个区间就至少包含一个 1。

所以以 i 结尾的含 1 区间数量就是 last1。注意这里不需要任何“减一”操作，因为左端点可以从 1 取到 last1，一共就是 last1 个。

继续用同样的 01 串 1, 0, 1, 1 验证：

• i = 1，bit = 1，last1 = 1，贡献 1，[1,1]；
• i = 2，bit = 0，last1 = 1，贡献 1，[1,2]；
• i = 3，bit = 1，last1 = 3，贡献 3，[1,3]、[2,3]、[3,3]；
• i = 4，bit = 1，last1 = 4，贡献 4，[1,4]、[2,4]、[3,4]、[4,4]。

累计 1 + 1 + 3 + 4 = 9。这个 01 串总共有 10 个子区间，唯一不含 1 的是 [2,2]，所以含 1 区间数等于 9，完全正确。

这个统计的单调性和 AND 是相反的：右端点固定时，只要左端点足够靠左就能包含 1，所以合法左端点是一个前缀区间 [1, last1]。

3.3 XOR：前缀异或状态计数，这个最需要细心

异或的“1 的个数为奇数”没有连续区间端点那么好处理，不能只靠一个 last 指针。这里需要用到前缀异或。

设 pre[i] = bit[1] ⊕ bit[2] ⊕ ... ⊕ bit[i]，特别的 pre[0] = 0。那么区间 [l, r] 的异或结果为：

bit[l] ⊕ ... ⊕ bit[r] = pre[r] ⊕ pre[l-1]

异或结果为 1，当且仅当 pre[r] 和 pre[l-1] 不相等。于是问题变成：枚举右端点 r，统计有多少个 j ∈ [0, r-1] 使得 pre[j] ≠ pre[r]。

维护两个计数器 cnt[0] 和 cnt[1]，分别表示已经遇到的 pre[0..r-1] 中 0 和 1 的个数。扫描到右端点 r，先算出当前前缀 pre[r]，然后异或为 1 的区间数量就增加 cnt[pre[r] ⊕ 1]，最后再把 cnt[pre[r]] 加一。

注意一开始要初始化 cnt[0] = 1，因为 pre[0] = 0 是存在的。

继续用 01 串 1, 0, 1, 1 验证：

• 初始 cnt[0]=1，cnt[1]=0；
• i=1，pre=1，答案加 cnt[0]=1，得到 [1,1]；
• i=2，pre=1，答案加 cnt[0]=1，得到 [1,2]；
• i=3，pre=0，答案加 cnt[1]=2，得到 [2,3]、[3,3]；
• i=4，pre=1，答案加 cnt[0]=2，得到 [4,4]、[1,4]。

累计 1 + 1 + 2 + 2 = 6。列出该 01 串所有子区间，异或为 1 的有 [1,1]、[3,3]、[4,4]、[1,2]、[2,3]、[1,4]，正好 6 个，完全吻合。

这个小例子其实暗中说明了一个容易犯错的点：区间 [l, r] 的异或值用的是 pre[l-1] 和 pre[r]，所以前缀位置 j 的范围是 0 到 n，比数组下标多了一个“空前缀”。忘了初始化 cnt[0] = 1 是大多数人写错 XOR 统计的原因。

3.4 三种统计放进同一次扫描

既然三位运算的统计都是扫一遍 01 串，那外层枚举二进制位，内层扫描数组时，可以同时维护 last0、last1、cnt[0]、cnt[1]，一次性把三个计数都算出来。伪代码如下：

for k = 0 to 30: last0 = 0, last1 = 0 cnt[0] = 1, cnt[1] = 0 pre = 0 cntAnd = cntOr = cntXor = 0 for i = 1 to n: bit = (a[i] >> k) & 1 // AND if bit == 0: last0 = i cntAnd += i - last0 // OR if bit == 1: last1 = i cntOr += last1 // XOR pre ^= bit cntXor += cnt[pre ^ 1] cnt[pre]++ sumAnd += cntAnd * (1LL << k) sumOr += cntOr * (1LL << k) sumXor += cntXor * (1LL << k)

这一段代码就是整道题的心脏。外层位数通常取 30，因为题目给的是 int 范围的非负整数；如果数据是 long long，那就取 60 或 63。内层 O(n) 扫描，总复杂度 O(30n)，空间只有几个变量。

4. 完整代码与常见提交坑：类型溢出、输出精度、边界检查

4.1 一份可以直接提交的 C++17 实现

下面给出完整代码，我加了一些注释，尽量把每个变量的作用写清楚：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; long long total = 1LL * n * (n + 1) / 2; long long sumAnd = 0, sumOr = 0, sumXor = 0; // int 范围内按 0~30 位处理 for (int k = 0; k <= 30; k++) { long long cntAnd = 0, cntOr = 0, cntXor = 0; int last0 = 0, last1 = 0; // 最近一个 0 / 最近一个 1 的位置 int cnt[2] = {1, 0}; // 前缀异或出现次数，cnt[0] 初始为 1 表示空前缀 int pre = 0; // 当前前缀异或值 for (int i = 1; i <= n; i++) { int bit = (int)((a[i] >> k) & 1LL); // 按位与：区间内全为 1 if (bit == 0) last0 = i; cntAnd += i - last0; // 按位或：区间内至少一个 1 if (bit == 1) last1 = i; cntOr += last1; // 按位异或：区间内 1 的个数为奇数 pre ^= bit; cntXor += cnt[pre ^ 1]; cnt[pre]++; } long long weight = 1LL << k; sumAnd += cntAnd * weight; sumOr += cntOr * weight; sumXor += cntXor * weight; } double ansAnd = (double)sumAnd / total; double ansOr = (double)sumOr / total; double ansXor = (double)sumXor / total; cout << fixed << setprecision(3); cout << ansAnd << " " << ansOr << " " << ansXor << "\n"; return 0; }

有些题目可能只要求输出某一种运算的期望，或者顺序不同，需要按题面调整。这里我按 AND、OR、XOR 三个都求来演示。

4.2 最容易踩的四个坑

第一个坑：long long 中间变量。n = 1e5 时，区间总数是大约 5e9，单个位上的 cntAnd 最大也是这个量级。再乘上 2^30（约 1e9），中间结果可能到 5e18，虽然 long long 上限约 9.22e18 还能撑住，但已经非常接近边界。如果题目 n 更大或者数据范围改用 long long，乘法结果甚至可能溢出 long long。稳妥的做法是：能用 long long 就用 long long，实在不行考虑 __int128。千万别用 int 去存统计量，这个错误相当隐蔽。

第二个坑：输出精度。期望输出通常保留三位小数。最稳妥的做法是先把贡献作为整数累加进 sumAnd、sumOr、sumXor，最后统一转换成 double 再除以 total。这样中间过程完全用整数，避免反复浮点运算带来的误差。不要每加一位就除一次 total，会积累精度问题。

第三个坑：位数范围。如果题目保证 a[i] 是非负 int，循环 k = 0..30 就够，因为 2^30 已经超过 1e9，int 最高位是符号位，实际数据不会用到那一位。如果数据范围是 long long，循环要到 63。总有人固定写 31 位然后数据一大就错，建议根据数据范围动态确定 k 的上限，比如先扫描数组最大值，再确定位数。

第四个坑：位运算优先级。写 (a[i] >> k) & 1 时括号不能省。C++ 里移位运算和按位与优先级容易混淆，不写括号轻则编译告警，重则结果完全不对。另外 1LL << k 一定要带 LL 后缀，否则 1 << 30 在某些平台会变成负数。

4.3 怎么验证自己没写错：暴力对拍

这类题我强烈建议写完正解后，本地写一个 O(n³) 的暴力去对拍。虽然 n 大了跑不动，但对于 n <= 50 的随机小数据，暴力完全可行。

for l = 1 to n: for r = l to n: andVal = a[l], orVal = a[l], xorVal = a[l] for t = l+1 to r: andVal &= a[t] orVal |= a[t] xorVal ^= a[t] sumAnd += andVal ...

拿同样的随机数组跑暴力，和拆位代码的结果对比。这个流程能帮你迅速排查出 last0、last1 初始化、cnt[0] 初始值、位数范围等细节错误。我第一次写这题的时候就是把 XOR 的 cnt[0] 初始值忘了，暴力对拍一秒就抓出来了。

4.4 复杂度分析：为什么这样写能过

外层枚举二进制位：int 范围下是 31 次。内层扫描数组：O(n)。总时间复杂度 O(31n)，在 n = 1e5 量级下非常轻松，几毫秒就能跑完。空间复杂度 O(1)，除了存原数组之外只用了常数个变量。

对比一下其他方案：直接用前缀和优化暴力能做到 O(n²)，n = 1e5 时依然不可行；用线段树维护位信息也许能处理带修改的版本，但静态统计下拆位 O(n) 扫描就是最优解之一。

5. 想举一反三？这类题都有同一个套路骨架

5.1 和这道题同构的常见题型

拆位法 + 区间计数这套组合，在算法竞赛里出现率非常高。我简单列几个同构题，你看到它们应该立刻想到同一套方法论：

• 给定数组，求所有连续子数组按位异或之和。这实际上就是本题 XOR 部分去掉随机区间、直接统计总贡献。
• 给定数组，求所有连续子数组按位与之和。同样只保留 AND 部分，维护 last0 统计。
• 给定数组，求所有连续子数组按位或之和。只保留 OR 部分，维护 last1 统计。
• 随机等概率选区间，求区间最大值/最小值期望。这个已经不是位运算了，但“统计合法区间数量”的思路和维护有效位置的单调性是一致的。

如果你已经把这些题做过一遍，再回头看 P10500，你会发现它只是把三种统计打包在一起，外层套了一个期望的外壳。

5.2 怎么识别“拆位 + 期望/总和”的套路

我自己的经验是，看到题目同时满足这三个条件，就基本确定可以用拆位法：

• 题目涉及位运算，尤其是 AND、OR、XOR；
• 问题涉及“所有子区间”或者“随机选择区间”的统计值或期望；
• 值域在 32 位或 64 位整数范围内。

一旦命中，拆位是默认起手式。先问自己：拆到某一位之后，这个 01 串上要统计什么？是全 1、含 1、奇数个 1，还是别的更复杂的条件？然后针对这个条件考虑，能不能通过维护 last 指针、前缀异或状态、前缀和、单调栈中的某一种来做 O(n) 扫描。

5.3 几个延伸思考方向

如果数组支持单点修改，这题会变成什么样？拆位之后每个位需要动态维护 last0、last1、前缀异或统计，这类操作可以用线段树维护区间合并信息来解决。每个节点维护区间内的 last0/last1 位置、前缀异或状态计数、异或值等，合并左右子树时就能 O(1) pushup。

如果数据范围不是 int 而是 long long，外层位数改成 63 就好，其他逻辑完全一样。如果数组长度到了 2e5 甚至 1e6，这个 O(位数 × n) 的算法依然能跑，只是常数和内存需要稍微注意一下。

另外一个容易忽略的优化是：在枚举位数之前先扫一遍数组，算出最大数的二进制位数，之后只枚枚举这些位，可以省掉数据很小时的无谓扫描。虽然对过题没太大影响，但写代码的时候顺手加一个 maxVal 判断，会让程序更严谨。

5.4 我个人建议的学习路线

如果你是被“期望”这两个字劝退才点进来的，我建议你按这个顺序消化这类题：

先把所有区间枚举出来的暴力写法写出来，理解期望就是“总和除以区间数”。然后只做 OR 部分的拆位统计，跑通之后再做 AND、XOR。最后再把三个统计合成一次扫描。拆开练的好处是，每个统计的错误都能被精确定位，而不是混在一起 debug。

我之前带过不少同学，他们最常犯的错误就是想着一次性把三个统计写对，结果数学推导和代码边界同时出错，最后只能对着错误输出瞎猜。其实这三个统计单独拿出来都不难，难的是把它们拼在一起时还能保持清醒。先拆开，再合并，效率会高很多。

做这类题还有一个习惯很值得培养：每写完一个扫描统计，就随便构造一个 01 串，手动列出所有子区间去验证。比如 1,0,1,1 这种长度 4 的串，总共才 10 个子区间，手算一遍只要几分钟，但能帮你把所有边界都验证清楚。这种笨办法在竞赛场上可能没时间做，但平时训练时极其有效，能帮你把“公式-代码”之间的信任关系彻底建立起来。