我到现在还记得第一次在题目列表里看见“P10500 Rainbow的信号”时的感受“期望”和“位运算”放在一起旁边还挂着“普及”第一反应是这题怕不是要搞什么高深概率论。但实际做下来它反而是我见过最适合用来理解拆位法和期望线性性的题目之一。题目本身不绕给一个长度为 n 的整数序列等概率随机选一组 l ≤ r把区间 [l, r] 的按位与、按位或、按位异或都作为“信号值”最后求这三个随机变量的数学期望。想通拆位法之后这道题就是 30 次 O(n) 扫描的事。这篇文章我把完整的推导链、计数方法和代码一并写出来适合刚接触期望类算法题、或者会写暴力但不知道怎么优化的读者。1. 先看懂题目在算什么东西随机区间和三种位运算1.1 期望不是洪水猛兽等概率场景下就是“全样本平均”很多同学看到“期望”两个字就开始慌其实这题的期望定义非常朴素。随机试验是从所有满足 1 ≤ l ≤ r ≤ n 的区间中等概率选一个总区间数显然是total n(n1)/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 序列。原本复杂的三种位运算在这一位上退化成非常直观的逻辑判断运算该位结果为 1 的条件等价说法AND区间内全部都是 1区间不包含任何 0OR区间内至少有一个 1区间包含至少一个 1XOR区间内 1 的个数为奇数区间前缀异或值不同这三句话是整个算法的核心。后面所有计数推导都只是这三个条件的组合数学应用。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 1bit 1last0 0贡献 1对应区间 [1,1]i 2bit 0更新 last0 2贡献 0i 3bit 1last0 2贡献 1对应区间 [3,3]i 4bit 1last0 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 1bit 1last1 1贡献 1[1,1]i 2bit 0last1 1贡献 1[1,2]i 3bit 1last1 3贡献 3[1,3]、[2,3]、[3,3]i 4bit 1last1 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]1cnt[1]0i1pre1答案加 cnt[0]1得到 [1,1]i2pre1答案加 cnt[0]1得到 [1,2]i3pre0答案加 cnt[1]2得到 [2,3]、[3,3]i4pre1答案加 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 一份可以直接提交的 C17 实现下面给出完整代码我加了一些注释尽量把每个变量的作用写清楚#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong 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 已经超过 1e9int 最高位是符号位实际数据不会用到那一位。如果数据范围是 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 l1 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 个子区间手算一遍只要几分钟但能帮你把所有边界都验证清楚。这种笨办法在竞赛场上可能没时间做但平时训练时极其有效能帮你把“公式-代码”之间的信任关系彻底建立起来。
我到现在还记得第一次在题目列表里看见“P10500 Rainbow的信号”时的感受“期望”和“位运算”放在一起旁边还挂着“普及”第一反应是这题怕不是要搞什么高深概率论。但实际做下来它反而是我见过最适合用来理解拆位法和期望线性性的题目之一。题目本身不绕给一个长度为 n 的整数序列等概率随机选一组 l ≤ r把区间 [l, r] 的按位与、按位或、按位异或都作为“信号值”最后求这三个随机变量的数学期望。想通拆位法之后这道题就是 30 次 O(n) 扫描的事。这篇文章我把完整的推导链、计数方法和代码一并写出来适合刚接触期望类算法题、或者会写暴力但不知道怎么优化的读者。1. 先看懂题目在算什么东西随机区间和三种位运算1.1 期望不是洪水猛兽等概率场景下就是“全样本平均”很多同学看到“期望”两个字就开始慌其实这题的期望定义非常朴素。随机试验是从所有满足 1 ≤ l ≤ r ≤ n 的区间中等概率选一个总区间数显然是total n(n1)/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 序列。原本复杂的三种位运算在这一位上退化成非常直观的逻辑判断运算该位结果为 1 的条件等价说法AND区间内全部都是 1区间不包含任何 0OR区间内至少有一个 1区间包含至少一个 1XOR区间内 1 的个数为奇数区间前缀异或值不同这三句话是整个算法的核心。后面所有计数推导都只是这三个条件的组合数学应用。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 1bit 1last0 0贡献 1对应区间 [1,1]i 2bit 0更新 last0 2贡献 0i 3bit 1last0 2贡献 1对应区间 [3,3]i 4bit 1last0 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 1bit 1last1 1贡献 1[1,1]i 2bit 0last1 1贡献 1[1,2]i 3bit 1last1 3贡献 3[1,3]、[2,3]、[3,3]i 4bit 1last1 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]1cnt[1]0i1pre1答案加 cnt[0]1得到 [1,1]i2pre1答案加 cnt[0]1得到 [1,2]i3pre0答案加 cnt[1]2得到 [2,3]、[3,3]i4pre1答案加 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 一份可以直接提交的 C17 实现下面给出完整代码我加了一些注释尽量把每个变量的作用写清楚#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong 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 已经超过 1e9int 最高位是符号位实际数据不会用到那一位。如果数据范围是 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 l1 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 个子区间手算一遍只要几分钟但能帮你把所有边界都验证清楚。这种笨办法在竞赛场上可能没时间做但平时训练时极其有效能帮你把“公式-代码”之间的信任关系彻底建立起来。
