自动搬运

查看原文

来自洛谷，原作者为

	Elaina_0 今朝依旧,今后亦然。

搬运于2025-08-24 22:58:36，当前版本为作者最后更新于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$ 最后出现的位置。

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

• $\operatorname{and}$ 的期望

  • 若第 $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$。

• $\operatorname{or}$ 的期望

  • 若第 $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}$$

• $\operatorname{xor}$ 的期望

  设 $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;
}