题解：P10500 Rainbow的信号

Usstzqqch_Iroha · 2025-08-21 11:00:33 · 题解

来源：《算法竞赛进阶指南》，李煜东著，\texttt{0x38}。

原题：\texttt{AcWing216}。

蒟蒻刚开始做的时候没看懂题解和小蓝皮。后来自己琢磨了一会自己就想通了（其实可能是书里的表述没太看懂），所以现在写一篇比较浅显的题解。

由于这可以算是数学期望的模板题，所以首先对于数学期望，我们来做一些解释。先来看前置知识。

随机事件 A：可能有多种结果的事件。
样本点：事件 A 的某种可能结果。
样本空间 \Omega：指某随机事件 A 的所有可能达成的状态（样本点）组成的集合。
概率 P(A)：指事件 A 发生的结果个数占总结果个数（即样本空间）的比重。
随机变量 X：将样本点映射为实数的函数。我们讨论取值有限的离散型随机变量。

有了这些知识，我们来了解数学期望的定义。

若随机变量 X 的取值有 x1,x2...，一个随机事件可表示成 X=X_i，其概率为 P(X=X_i)=p_i，则称 E(x)=\Sigma p_ix_i 为随机变量 X 的数学期望。摘自《算法竞赛进阶指南》，李煜东著。

说白了，数学期望就是带权求和，只是权值变成了事件发生的概率，这需要你自己求；而随机变量通常题目里面会给你求法或者定义。

譬如：本题当中给定了你随机变量 X 的求法，即任意选定的区间 [L,R] 中所有的 N_i 的按位 \text{xor,or,and} 和，而概率则需自己计算。

首先计算概率。根据题意，显然 l<r 时会有一个 r<l 的对称情况，P(A)=\displaystyle \frac{1}{n}\times \displaystyle \frac{1}{n}\times 2 = \displaystyle \frac{2}{n^2} 。同理 l=r 时 P(A)=\displaystyle \frac{1}{n^2}。

现在的问题就是处理区间内的位运算。显然采用前缀异或/与/或数组会达到 O(n^2) 的时间复杂度，会爆。考虑到位运算不进位，我们可以将整数转换为二进制，按位进行计算，最后合并每一位的贡献即可。

有了这个思路，接下来就是分类讨论了。（然后挂了我很久）

首先我们设目前枚举到了N_i 的第 k 个二进制数位（从 1 开始）为右边界，目前称之为 B_i（因为我们之后还要更新）。我们先对朴素的按位与和按位或进行讨论。

记该位之前数字 g 最后一次出现过的位置为 last[g]，那么我们稍加思索可以推出以下结论：

按位或：当 B_i=1 时，对于任意的 l\le r，区间 [l,r] 内的 \text{or} 和的结果一定为 1。这是因为按位或“有 1 全 1”的性质（即 1\ \text{or}\ x = 1）。此时将 2^{k-1}\times P(A)\times (r-1) 累加到 \text{or} 的答案中。
按位与：当 B_i=0 时，对于任意的 l\le r，区间 [l,r] 内的 \text{and} 和的结果一定为 0。这是因为按位与“有 0 全 0”的性质（即 0\ \text{and}\ x=0）。此时对 \text{and} 的答案什么都不做。
当 B_i=0 时，将 2^{k-1}\times P(A)\times last[1] 累加到 \text{or} 的答案中（如果出现过 1 的话）。
当 B_i=1 时，将 2^{k-1}\times P(A)\times (k-last[0]-1) 累加到 \text{and} 的答案中（如果出现过 0 的话）。

接下来我们开始讨论 \text{xor} 的情况。

我们知道 \text{xor} 运算和其它运算都不太一样。 \text{xor} 运算不仅仅和当前数位有关，它和前面的所有数位 \text{xor} 的结果也有关系。所以我们可以开两个变量 c_0、c_1 来记录所有的 l 的个数，分别满足 \text{xor}^{k-1}_{i=l} B_i=0 和 \text{xor}^{k-1}_{i=l} B_i=1。那么当 B_i=0 时，将 2^{k-1}\times P(A)\times c_1 累加到答案中，反之将 2^{k-1}\times P(A)\times c_0 累加到答案中，并需要将 c_0 和 c_1 进行交换（因为原来 [l,k-1] 的 \text{xor} 结果为 0，\text{xor}\ 1 运算过后结果变成了 1，而原来 c_1 对应的区间 \text{xor} 的结果就变成了 0）。注意我们需要在交换之前 c_0\gets c_0+1 来更新之后的 c_1。

代码其实写出来也差不多，但还是粘上来吧。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n;
int N[maxn];
int pre_xor[maxn],pre_and[maxn],pre_or[maxn];
int /*B[maxn],*/last[2];//开一个B变量就够了
double ans_xor,ans_and,ans_or;
int maxk = -1,len;
/*int calc(int x){
    int y=x;
    len = 0;
    while(y){
        y>>=1;
        len++;
    }
    return len;
}*/
//试图计算最大位数发现没有必要 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>N[i];
    }
    /*for(int i=1;i<=n;i++){
        maxk = max(maxk,calc(N[i]));
    }*/
  //调试代码
    int c1,c2;
    for(int k=0;k<=30;k++){//这里是从第0位开始的
        last[0]=0;
        last[1]=0;
        c1=0;
        c2=0;
        for(int i=1;i<=n;i++){
            int B = (N[i]>>k)&1;
            double ret = (double)(1<<k)/(n*n);
            if(B==0){
                ans_and+=ret+2.0*ret*(i-last[0]-1);
                ans_or+=ret+2.0*ret*(i-1);
                ans_xor+=ret+2.0*ret*c1;
            }
            else{
                ans_or+=2.0*ret*last[1];
                ans_xor+=2.0*ret*c2;
            }//按上面的结论模拟
            last[B]=i;
            c1++;
            if(B) swap(c1,c2);
        }
    }
    printf("%.3f %.3f %.3f",ans_xor,ans_and,ans_or);
}

一些提醒

注意浮点数类型不要开 \texttt{long double}。因为你会发现你的程序除了 0.000 什么都不输出。~~是的我第一遍就挂在这里~~
涉及乘法，记得开 \texttt{long long}。否则你会由 40\gets 100，这很不好笑。实例。