Rainbow的信号

形式化题目

给定长度为 $N$ 的自然数序列 $a_1, a_2, \dots, a_N$ 。在 $1 \dots N$ 中等概率地取两个数 $l, r$ ，若 $l > r$ 则交换，于是有序对 $(l, r)$ 在 $N^2$ 个可能取值上均匀分布。取出子段 $P = (a_l, \dots, a_r)$ ，记

$$\operatorname{op}(l, r) = \text{$ P$ 中所有元素的 op 运算结果}, \qquad \operatorname{op} \in {\oplus, &, |}.

要求分别计算三个数学期望

E_\oplus = \frac{1}{N^2} \sum_{l=1}^{N} \sum_{r=1}^{N} \bigoplus_{i=l}^{r} a_i, \qquad E_\& = \frac{1}{N^2} \sum_{l=1}^{N} \sum_{r=1}^{N} \bigwedge_{i=l}^{r} a_i, \qquad E_| = \frac{1}{N^2} \sum_{l=1}^{N} \sum_{r=1}^{N} \bigvee_{i=l}^{r} a_i .

三条运算都是逐位独立的：结果的第 $k$ 位只由各元素第 $k$ 位决定。这把问题切成 30 个互不相干的一位 0/1 子问题，是整道题的骨架。

正解

思路

题面的两个量级决定了整条路线： $N \leqslant 10^5$ 说明区间个数 $N^2$ 不可枚举， $a_i \leqslant 10^9 < 2^{30}$ 说明"按位拆成 30 列"的代价极小。

朴素做法的瓶颈在区间个数。 最直接的做法是枚举所有有序对 $(l, r)$ ，对每个区间扫一遍求三个 op 值：

text

1
2
3for l in 1..N:
    for r in 1..N:
        扫描 a[l..r] 求 xor / and / or

即使边扩右端点边维护、让每个区间做到 $O(1)$ ，区间个数本身就是 $N^2 = 10^{10}$ ， $N = 10^5$ 时怎么优化常数都跑不完。要消除的不是扫描，而是"枚举区间"这件事本身。

第一步：按位拆分。 xor、and、or 都是逐位定义的运算，第 $k$ 位的结果只取决于各元素第 $k$ 位。所以把每个数写成二进制，把序列看成一个 $30 \times N$ 的 0/1 矩阵：

a_i = \sum_{k} 2^k b_{k,i}, \qquad b_{k,i} = \left\lfloor \frac{a_i}{2^k} \right\rfloor \bmod 2 .

由于按位展开后求和可以交换次序，

\sum_{l, r} \operatorname{op}(l, r) = \sum_{k} 2^k \sum_{l, r} \operatorname{op}_k(l, r),

其中 $\operatorname{op}_k(l, r)$ 是把第 $k$ 位抽成 0/1 串后算出的 op 值（0 或 1）。每一列独立解决，最后加权相加。

第二步：一位上的三种统计。 固定一位，设抽出的 0/1 串是 $b_1 \dots b_N$ 。把它压缩成同值连续段：值为 1 的段长为 $L_1, L_2, \dots$ ，值为 0 的段长为 $Z_1, Z_2, \dots$ 。三种运算的取值条件都只与"区间落在什么段里"有关：

运算	区间结果为 1 的条件	$l \leqslant r$ 的区间个数
and	区间内全是 1，即区间完整落在某个 1 段内	$S_{\mathrm{and}} = \sum_i \dfrac{L_i(L_i+1)}{2}$
or	区间内至少一个 1；用全集减掉"全是 0"	$S_{\mathrm{or}} = \dfrac{N(N+1)}{2} - \sum_j \dfrac{Z_j(Z_j+1)}{2}$
xor	区间内有奇数个 1，等价于 $P_{l-1} \neq P_r$	$S_{\mathrm{xor}} = c_0 \cdot c_1$

最后一行里的 $P$ 是前缀异或： $P_0 = 0$ ， $P_i = b_1 \oplus b_2 \oplus \dots \oplus b_i$ 。因为区间异或 $= P_r \oplus P_{l-1}$ ，它为 1 当且仅当两个前缀值不同；于是只要统计 $P_0, \dots, P_N$ 里 0 出现 $c_0$ 次、1 出现 $c_1$ 次，答案就是 $c_0 c_1$ 。

关键在于 $c_0, c_1$ 不需要逐格扫前缀。 $P_i$ 只在前缀扫过一个 1 时才翻转：

遇到长度 $L$ 的 1 段：段内 $P$ 逐格交替，前 $\lceil L/2 \rceil$ 格翻到对面，后 $\lfloor L/2 \rfloor$ 格落回原值，出段时按 $L$ 的奇偶决定新的前缀值；
遇到长度 $L$ 的 0 段： $P$ 一个都不变， $L$ 格全部计入当前值一侧。

这样一位上的全部统计只需遍历段表，段数最多 $N$ ，整个过程是线性的。

第三步：换回有序对口径。 上面统计的是 $l \leqslant r$ 的无序区间。题目取的是有序对： $l < r$ 的区间在 $N^2$ 个有序对里出现 2 次， $l = r$ 的单点区间只出现 1 次，而单点区间的三种 op 都等于那个元素本身。逐位看，单点中 op 结果为 1 的正是该位上值为 1 的位置，设共 $T_k$ 个，于是

\sum_{l=1}^{N}\sum_{r=1}^{N} \operatorname{op}_k(l,r) = 2 S_k - T_k .

其中 $S_k$ 取上表中 and / or / xor 三种计数中对应的那一个。分母始终是 $N^2$ ，不是 $\frac{N(N+1)}{2}$ 也不是 $C_N^2$ ，这是最容易错的一处。

用样例 $N = 2$ 、 $a = (4, 5)$ 把上面的推导完整验证一遍：先枚举有序对，再按位拆分。四个有序对的原始结果：

$(l, r)$	子段 $P$	xor	and	or
$(1, 1)$	$4$	4	4	4
$(1, 2)$	$4, 5$	1	4	5
$(2, 1)$	$5, 4$	1	4	5
$(2, 2)$	$5$	5	5	5
总和		11	17	19
除以 $N^2 = 4$		2.750	4.250	4.750

再看按位拆分。低三位以外的位全是 0，逐位加权正好还原上面的总和：

位 $k$	位权 $2^k$	该位 0/1 串	$S_{\mathrm{and}}$	$S_{\mathrm{or}}$	$S_{\mathrm{xor}}$	$T_k$	and 贡献 $2S_{\mathrm{and}} - T_k$	or 贡献	xor 贡献
0	1	`0 1`	1	2	2	1	1	3	3
1	2	`0 0`	0	0	0	0	0	0	0
2	4	`1 1`	3	3	2	2	4	4	2
加权求和							$1+0+16 = 17$	$3+0+16 = 19$	$3+0+8 = 11$

第 2 位是全 1 段， $S_{\mathrm{and}} = 3$ 对应三个无序区间 $[1,1],[1,2],[2,2]$ ；and 的加权 $2 \times 3 - 2 = 4$ 就是这个位上全部有序对的贡献，乘位权 4 得 16。

整体路线如下：

text

1
2
3
4
5
6
7
8
9
10
11
12
13N 个数 a_1..a_N
   │  写成定长 30 位二进制，首尾相接
   ▼
30 × N 的 0/1 矩阵  ──按列切片──▶  第 k 位的 0/1 串
                                        │
                                        ├─ 连续段表 ─▶ S_and / S_or / c0·c1
                                        │
                                        └─ 2S - T  ─▶ 该位贡献 × 2^k
   ▲                                                         │
   └──────────────── 30 列加权求和 ◀──────────────────────────┘
   │
   ▼
总和 / N^2  ─▶ 三个期望（保留 3 位小数）

推导中的量落到代码里是这样的：定长二进制矩阵是 packed，按列切片是 packed[k::WIDTH]；连续段表是 runs； $S_{\mathrm{and}}$ 与 $S_{\mathrm{or}}$ 分别是 all_one 和 total - all_zero； $S_{\mathrm{xor}}$ 是 seen[0] * seen[1]（seen 在遍历 runs 时按段累计前缀异或 $P$ 取两种值的次数）； $T_k$ 是 singles；有序对修正与位权加权收在 one_bit_values 的返回值与 solve() 的求和式里。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 16:43
# update_at: 2026-10-01 17:00

import re
import sys

WIDTH = 30  # 10^9 < 2^30，定长二进制串才能按列切片取出每一位


def one_bit_values(column: str) -> tuple[int, int, int]:
    """一位上的三份加权分子：column 是该位按原下标顺序拼成的 0/1 串。

    xor / and / or 的每份答案都是「所有区间的该位值（0 或 1）之和」，
    而三种运算的取值都只由同值连续段的长度决定，所以先压缩成段长表再统计。
    """
    runs = [(int(part[0]), len(part)) for part in re.findall("0+|1+", column)]
    ones = [length for value, length in runs if value]
    zeros = [length for value, length in runs if not value]
    all_one = sum(length * (length + 1) // 2 for length in ones)    # 全是 1 的区间数 = and 为 1 的区间数
    all_zero = sum(length * (length + 1) // 2 for length in zeros)  # 全是 0 的区间数
    total = len(column) * (len(column) + 1) // 2                    # 区间总数

    # 前缀异或 P_i 只在扫过 1 时翻转：1 段内部逐格交替，0 段内部保持不变。
    # P 取到 0 的次数乘取到 1 的次数，就是 xor 为 1 的区间数。
    parity, seen = 0, [1, 0]  # P_0 = 0，先计入偶侧
    for value, length in runs:
        if value:
            seen[parity] += length // 2              # 段内交替，后 floor(L/2) 个落回原奇偶
            seen[parity ^ 1] += (length + 1) // 2    # 前 ceil(L/2) 个翻到对面
            parity ^= length & 1                     # 段的奇偶长度决定出段时的前缀值
        else:
            seen[parity] += length                   # 0 段不改变前缀值

    # 长度大于 1 的区间有 (l, r) 两种取法，单点区间只有一种，故加权数为 2c - s
    singles = sum(ones)  # 该位上 1 的个数 = 单点区间里 op 结果为 1 的个数
    return tuple(2 * count - singles for count in (seen[0] * seen[1], all_one, total - all_zero))


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    signal = [next(data) for _ in range(n)]

    # 全部数拼成 WIDTH 位定长串：按列切片就一次拿到所有位的 0/1 序列
    packed = ''.join(f'{value:0{WIDTH}b}' for value in signal)
    parts = [one_bit_values(packed[k::WIDTH]) for k in range(WIDTH)]

    # 按位独立：第 k 列的位权是 2^(WIDTH-1-k)（最高位在最左），30 列加权相加即三份答案
    totals = [sum(part[i] << (WIDTH - 1 - k) for k, part in enumerate(parts)) for i in range(3)]
    # 分母是 (l, r) 的有序取法总数 N^2，与上面的加权计数口径一致
    print(' '.join(f'{total / n ** 2:.3f}' for total in totals))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:35
 * update_at: 2026-10-06 18:35
 */
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // N 最大 1e5
const int WIDTH = 30;    // a_i < 2^30，逐位拆成 30 列

ll n;
ll a[MAXN]; // 题目给出的信号，下标从 1 开始
ll run_value[MAXN];  // 某一列压缩后的连续段取值（0/1）
ll run_length[MAXN]; // 对应连续段的长度

// 计算第 k 位上的三种「有序区间计数」（未乘位权）：
// 把该位抽成 0/1 串并压缩成同值连续段，由段长得到 and / or 的区间数；
// 再由前缀异或取值次数得到 xor 的区间数，最后用 2S-T 换成有序对口径。
void count_one_bit(int k, ll &cnt_xor, ll &cnt_and, ll &cnt_or) {
    int seg = 0; // 连续段个数
    int i = 1;
    while (i <= n) {
        ll value = (a[i] >> k) & 1;
        int j = i;
        while (j <= n && ((a[j] >> k) & 1) == value) {
            j++;
        }
        seg++;
        run_value[seg] = value;
        run_length[seg] = j - i;
        i = j;
    }

    ll all_one = 0;  // 完整落在 1 段内的区间数，即 and 为 1 的无序区间数
    ll all_zero = 0; // 完整落在 0 段内的区间数
    ll ones = 0;     // 该位上 1 的个数，等于单点区间里结果为 1 的个数
    for (int t = 1; t <= seg; t++) {
        ll len = run_length[t];
        if (run_value[t] == 1) {
            all_one += len * (len + 1) / 2;
            ones += len;
        } else {
            all_zero += len * (len + 1) / 2;
        }
    }
    ll total = n * (n + 1) / 2; // l <= r 的无序区间总数

    // 前缀异或 P_i 只在扫过 1 时翻转：1 段内逐格交替，0 段内保持不变。
    ll seen[2] = {1, 0}; // P_0 = 0，先计入取值 0 的一侧
    int parity = 0;
    for (int t = 1; t <= seg; t++) {
        ll len = run_length[t];
        if (run_value[t] == 1) {
            seen[parity] += len / 2;
            seen[parity ^ 1] += (len + 1) / 2;
            parity ^= len & 1;
        } else {
            seen[parity] += len;
        }
    }

    ll un_xor = seen[0] * seen[1]; // 区间异或为 1 的无序区间数
    ll un_and = all_one;
    ll un_or = total - all_zero; // 全集减掉全 0 区间，即含 1 的区间数
    // 长度大于 1 的区间在有序对里出现两次，单点区间只出现一次
    cnt_xor = 2 * un_xor - ones;
    cnt_and = 2 * un_and - ones;
    cnt_or = 2 * un_or - ones;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long double sum_xor = 0.0L;
    long double sum_and = 0.0L;
    long double sum_or = 0.0L;
    long double bit_value = 1.0L; // 当前位的位权 2^k
    for (int k = 0; k < WIDTH; k++) {
        ll cnt_xor, cnt_and, cnt_or;
        count_one_bit(k, cnt_xor, cnt_and, cnt_or);
        sum_xor += bit_value * cnt_xor;
        sum_and += bit_value * cnt_and;
        sum_or += bit_value * cnt_or;
        bit_value *= 2.0L;
    }

    long double denom = n;
    denom = denom * n; // 分母是有序对总数 N^2
    printf("%.3Lf %.3Lf %.3Lf\n", sum_xor / denom, sum_and / denom, sum_or / denom);
    return 0;
}

复杂度

时间：打包是 $O(30N)$ ，按列切片 30 次 $O(N)$ ，每列求连续段与统计也是 $O(N)$ ，总计 $O(30N)$ ，即 $O(N \log A)$ （ $A$ 为值域上界）。 $N = 10^5$ 时约 $3 \times 10^6$ 次基本操作，远快于朴素做法的 $O(N^2)$ 。
空间：packed 占 $30N$ 个字符，加上读入的整数列表，以及每列临时产生的切片与段表，总量仍是 $O(30N)$ ；实测 $N = 10^5$ 时峰值约 33MB。

总结

按位拆分是位运算期望题的通用起手式：xor / and / or 逐位独立，把 30 位拆成 30 个独立的 0/1 计数问题，值域的对数只有 30，代价极小。
一位上的三种统计各自有明确的结构刻画：and 数"全是 1 的区间"、or 数"含 1 的区间"（用全集减去全 0 段）、xor 数"前缀异或取值不同的下标对"。前两者只需连续段长度，后者只需每段对 $P$ 取值的分摊次数。
统计的是无序区间时，务必用 $\text{有序贡献} = 2S - T$ 换回题目口径，分母是 $N^2$ 。

目录

形式化题目

正解

思路

代码

复杂度

总结