转化题意

拿到题目就看到了数学期望，但是分析后发现其实就是算出所有区间每个数按位与、按位或、按位异或和。

值得注意的是，他是等概率的选取左右端点，如果 $l>r$ 他就会交换，所以长度大于一的区间贡献应该乘二。

由于是在比赛中做的题，我将不是很详细地简要分析从部分分到正解的过程和可能导致挂分的原因。

20分

$n$ 才 $100$,枚举区间左右端点然后算，复杂度 $O(n^3)$ 就不展示代码了。

40分

这个时候 $O(n^3)$ 肯定过不去了，但是 $O(n^2)$ 可以过去，突然想到区间 DP 的时候做的操作，用小区间推大区间。

if(n<=1000) {
	double ans1,ans2,ans3;
	for(int i=1; i<=n; ++i) {
		dp[i][i][0]=dp[i][i][1]=dp[i][i][2]=a[i];
	}
	for(int len=2; len<=n; ++len) {
		for(int l=1; l+len-1<=n; ++l) {
			int r=l+len-1;
			dp[l][r][0]=dp[l+1][r][0]^a[l];
			dp[l][r][1]=dp[l+1][r][1]&a[l];
			dp[l][r][2]=dp[l+1][r][2]|a[l];
			ans1+=dp[l][r][0]*2.0/n/n;
			ans2+=dp[l][r][1]*2.0/n/n;
			ans3+=dp[l][r][2]*2.0/n/n;
		}
	}
	printf("%.3lf %.3lf %.3lf\n",ans1,ans2,ans3);
	ans1=ans2=ans3=0;
	return 0;
}

其中 $ans1$、$ans2$、$ans3$ 分别代表异或、与、或的答案，先加起来最后除。与 $dp$ 数组第三维下标 $0$,$1$,$2$ 分别对应，一开始 $ans$ 提前加上长度为 $1$ 的区间的值，后面 $len$ 从 $2$ 开始。

70分

70分的特殊条件

$N$ 个数为 $0$ 或 $1$

这已经非常接近正解了。

这个时候我们要按位考虑，如果我们从 $1$ 到 $n$ 枚举以每一位为结尾，他的贡献就操作后能够形成结果是 $1$ 的区间的数量的两倍（前面说过了），区间长度为 $1$ 的仍然预处理。

先考虑异或，异或是一种奇特的操作，怎么样可以让结果为 $1$？$1$个数为奇数就行。考虑每一个 $1$他前面肯定跟若干个 $0$（可能是 $0$ 个），把每个 $1$ 和这若干个 $0$ 分成一组，之后能当左端点的区间肯定是隔一个取一个的。

比如说我们现在到了这个黄色的 $1$，能贡献的就是红色部分的长度。当考虑到了一后面的 $0$ ，贡献就变成了红色加黄色的长度。

我们用 $g$ 数组记录长度，$l$ 表示要加的话加哪一个。

如果这一位是 $1$

ans1+=g[l];
g[l]++;
l^=1;

注意这里 $l$ 要在 $g$ 数组加了之后再变。 否则：

ans1+=g[l^1];
g[l]++;

这为啥要 $l$ 异或 $1$，因为上一次碰见 $1$ 的时候 $l$ 已经变化了，但还是要加原来的。

现在考虑与和或，都很简单。因为只要有一个 $1$,或结果就是 $1$ ，按位与与正好相反，让 $lst_i$ 为 $i$（$0$ 或 $1$）。

这样如果这一位是 $1$。

ans2+=i-1-lst[0];//到左边第一个0之前都行
ans3+=i-1;//这一位已经是一了，前面的都行

否则

ans3+=lst[1];//左端点必须在从开头到从左往右最后一个1之间

//这一位已经是0所以按位与结果一定是0，不用管

每次循环一次后，更新 $lst$ 的值即可。

正解100分

前面的做出来后正解就很简单了，只需把 $a_i$ 按位拆开，假设这是第 $j$ 位，每一次算的时候乘上 $2^{j-1}$ 就好了。

#include<bits/stdc++.h>
#define R(x) x=read()
#define int long long
#define N 100005
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e-'0');
		e=getchar();
	}
	return x*y;
}
int n,a[N];
bool f[N][35];
int mx;
int dp[1005][1005][3];
int ans1,ans2,ans3;
main() {
	R(n);
	for(int i=1; i<=n; ++i) {
		R(a[i]);
		int t=a[i],j=0;
		while(t) {
			f[i][++j]=t&1;
			t>>=1;
		}
		mx=max(mx,j);
	}
	int lst[2],g[2],l;
	for(int j=1; j<=mx; ++j) {
		lst[0]=lst[1]=g[0]=g[1]=0,l=0;
		for(int i=1; i<=n; ++i) {
			if(f[i][j]==1) {
				ans1+=g[l]*(1ll<<(j-1));
				g[l]++;
				l^=1;
				ans2+=(i-1-lst[0])*(1ll<<(j-1));
				ans3+=(i-1)*(1ll<<(j-1));
			} else {
				ans1+=g[l^1]*(1ll<<(j-1));
				g[l]++;
				ans3+=lst[1]*(1ll<<(j-1));
			}
			lst[f[i][j]]=i;
		}
	}
	ans1<<=1;
	ans2<<=1;
	ans3<<=1;
	for(int i=1; i<=n; ++i) {
		ans1+=a[i];
		ans2+=a[i];
		ans3+=a[i];
	}
	printf("%.3lf %.3lf %.3lf\n",(double)ans1/(n*n),(double)ans2/(n*n),(double)ans3/(n*n));
	return 0;
}

进食后人

$ans$ 一定不要用 $double$，加的时候用整形的（最好用 $long \space long$ 因为我的代码不开全 WA)

我赛时用的 $double$ 导致挂了最后30。

警钟吃掉。

套路的，枚举值域内每个二进制位，然后求出所有情况的和。

• 对于 $\operatorname{xor}$，显然可以用两个变量统计这一位异或出来等于 $1$ 和 $0$ 的个数，每遇到一个 $1$，交换上述变量，遇到 $0$ 则不变，然后对应变量 $\gets +1$。

• 对于 $\operatorname{and}$，显然只与上一次出现 $0$ 的位置有关。

• 对于 $\operatorname{or}$，显然只与上一次出现 $1$ 的位置有关。

分别计算出贡献，最后 $\div n^2$ 即可。

注意特殊处理一下 $l=r$ 时的贡献（视实现方式而定，多算了减掉，少算了加上）。

代码：

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10;
ll n,a[N],mx=-1;
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){cin>>a[i];mx=max(mx,a[i]);}
	ll ans1,ans2,ans3;
	ans1=ans2=ans3=0;
	for(ll i=0;(1LL<<i)<=mx;i++){
		ll ze=0,on=0,lst0=0,lst1=0;
		for(ll j=1;j<=n;j++){
			if(a[j]&(1LL<<i)){swap(ze,on),on++;lst1=j;}
			else{ze++;lst0=j;}
			ans1+=on*(1LL<<i)*2;
			ans2+=(j-lst0)*(1LL<<i)*2;
			ans3+=lst1*(1LL<<i)*2;
		}
	}
	for(ll i=1;i<=n;i++) ans1-=a[i],ans2-=a[i],ans3-=a[i];
	double as1=(double)ans1/(double)(n*n),as2=(double)ans2/(double)(n*n),as3=(double)ans3/(double)(n*n);
	printf("%.3lf %.3lf %.3lf",as1,as2,as3);
	return 0;
}