题解：P10500 Rainbow的信号

Elaina_0 · 2024-05-24 17:01:11 · 题解

P10500 Rainbow的信号

谢谢管理大大的审核，

顺便无耻的推一下 blog。

思路

因为位运算当前位的结果只与当前位有关，所以可以单独考虑每一位，最后将每一位的贡献相加就是答案。

由于 l，r 是等概率选取，所以选取长度为 1 的区间（l = r）的概率是 \frac{1}{n^2}，选取其他区间（l \neq r）的概率是 \frac{2}{n^2}。

设 a_i,a_j 表示第 i 个数字的第 j 个二进制位的值；last[k] (k=0,1) 表示 k 最后出现的位置。

分别讨论三种运算的期望：

• - 若第 $x$ 个数字的第 $k$ 位是 $1$，以 $x$ 为右端点，在 $[last[0]+1,r]$ 区间内任取两个数组成的区间 $\operatorname{and}$ 和都是 $1$，因此她的贡献为： $$\begin{cases} last[0] = x 　2^k \times \frac{1}{n^2}\\ last[0]+1 \neq x　2^k \times (x-(last[0]+1)) \times \frac{2}{n^2} \end{cases}$$ - 若第 $x$ 个数字的第 $k$ 为是 $0$，不存在左端点与 $x$ 的组合使得区间的 $\operatorname{and}$ 和为 $1$。
• - 若第 $x$ 个数字的第 $k$ 位是 $1$，前面所有点都可以与 $x$ 组成区间使得 $\operatorname{or}$ 和为 $1$，所以她的贡献为： $$\begin{cases} l = x　2^k \times \frac{1}{n^2}\\ l \neq x　2^k \times (x−1) \times \frac{2}{n^2} \end{cases}$$ - 若第 $x$ 个数字的第 $k$ 位是 $0$，以 $x$ 为右端点，$≤last[1]$ 的数字可以选作左端点，所以她的贡献为： $$2^k \times last[1] \times \frac{2}{n^2}$$
• 设 $t$ 是 $[l,x]$ 区间的 $\operatorname{xor}$ 和, $c1$ 表示 $[l,x]$ 区间 $\operatorname{xor}$ 和为 $0$ 的 $l$ 个数，$c2$ 表示 $[l,x]$ 区间 $\operatorname{xor}$ 和为 $1$ 的 $l$ 个数。 从 $l = x$ 开始，将 $l$ 向左移动，若第 $l$ 位是 $1$ 则 $t$ 取反，否则 $t$ 不变。 - 若第 $x$ 个数字的第 $k$ 位是 $1$，则 $l$ 只能选择 $c1$ 表示的部分，所以她的贡献为： $$2^k \times c1 \times \frac{2}{n^2}$$ - 若第 $x$ 个数字的第 $k$ 位是 $0$，则 $l$ 只能选择 $c2$ 表示的部分，所以她的贡献为： $$2^k \times c2 \times \frac{2}{n^2}$$ 最后还要加上 $l = x$ 的贡献： $$2^k \times \frac{1}{n^2}$$ 当右端点 $r$ 增加 $1$，令 $c1$ 增加 $1$。 若 $a[r] = 1$，则还需交换 $c1,c2$。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Elaina 0
const int N=100010;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

int n,a[N];
int last[3],c1,c2;
double ansand,ansor,ansxor;

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

    for(int i=0;i<=30;i++){
        last[0]=last[1]=0;
        c1=c2=0;
        for(int j=1;j<=n;j++){
            int now=(a[j]>>i)&1;
            double ret=(double)(1<<i)/(n*n);
            if(now){
                ansand+=ret+2.0*ret*(j-(last[0]+1));
                ansor+=ret+2.0*ret*(j-1);
                ansxor+=ret+2.0*ret*c1;
            }else{
                ansor+=2.0*ret*last[1];
                ansxor+=2.0*ret*c2;
            }
            last[now]=j;
            c1++;
            if(now) swap(c1,c2);
        }
    }

    printf("%.3lf %.3lf %.3lf",ansxor,ansand,ansor);
    return Elaina;
}