Contest Hunter 3801 Rainbow的信号

题面

题意

给出 n n n个数，随机rand两个1~n的数 l l l, r r r，若 l > r l>r l>r，则交换两数，求区间 [ l , r ] [l,r] [l,r]中的数异或，与，或的值的期望。

做法

首先因为是位运算，因此我们可以逐位考虑，对每一位单独计算，下面考虑第 u + 1 u+1 u+1位：

可以发现长度为1的区间被rand到的概率均为 1 / n / n 1/n/n 1/n/n，长度大于1的区间被rand到的概率均为 2 / n / n 2/n/n 2/n/n，因此我们要分开来处理。

对于长度为1的区间，很好处理，如果这位是1，对三个答案都加上 ( 1 &lt; &lt; u ) ∗ 1 / n / n (1 &lt;&lt; u)*1/n/n (1<<u)∗1/n/n，反之不对答案做出任何贡献。

对于长度大于1的区间，我们可以枚举右端点，并记录0和1上一次出现的位置，然后计算三个答案：

1.与：只有连续的一段1才行，因此答案为 ( i − p o s [ 0 ] − n u m [ i ] ) ∗ 2 / n / n (i-pos[0]-num[i])*2/n/n (i−pos[0]−num[i])∗2/n/n，注意要减去长度为1的区间的贡献。

2.或：只要区间中有1即可，因此答案为 ( p o s [ 1 ] − n u m [ i ] ) ∗ 2 / n / n (pos[1]-num[i])*2/n/n (pos[1]−num[i])∗2/n/n。

3.异或：可以发现合法的左端点是相间的区间，每个区间有一些0（可以没有）和一个1组成，因此用两个变量分别维护这两种区间的数的个数，然后每次计算贡献即可，具体可以参考代码。

代码

#include<iostream>
#include<cstdio>
#define db double
#define N 100100
using namespace std;

int n,num[N],tmp[N];
db an1,an2,an3;

inline void solve(int u)
{
	int i,j,pos[2],cnt[2];
	bool now=0;
	db t;
	for(i=1;i<=n;i++)
	{
		if(num[i]&(1 << u))
		{
			tmp[i]=1;
			an1+=(1 << u)*1./n/n;
			an2+=(1 << u)*1./n/n;
			an3+=(1 << u)*1./n/n;
		}
		else tmp[i]=0;
	}
	cnt[0]=cnt[1]=pos[0]=pos[1]=0;
	for(i=1;i<=n;i++)
	{
		pos[tmp[i]]=i;
		cnt[now]++;
		an1+=(1 << u)*2./n/n*(cnt[now^(!tmp[i])]-tmp[i]);
		an2+=(1 << u)*2./n/n*(i-pos[0]-tmp[i]);
		an3+=(1 << u)*2./n/n*(pos[1]-tmp[i]);
		now^=tmp[i];
	}
}

int main()
{
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++) scanf("%d",&num[i]);
	for(i=0;i<30;i++) solve(i);
	printf("%.3f %.3f %.3f",an1,an2,an3);
}