位与位间互不影响。一位一位计算。

长度为 $1$ 的区间，选出概率为 $1/n^2$。其余区间，选出概率为 $2/n^2$。（这里的区间 $l \leq r$）

枚举右端点。记 $last_0$ 表示 $0$ 上一次出现的位置。 $last_1$ 同样。

下面我们只研究区间长度不为 $1$ 的。为 $1$ 的话直接计上就好了。

对于 $\mathrm{and}$ 和，倘若当前数的这一位为 $0$ 则不用计算，否则，左端点在 $[last_0+1,now-1]$ 间的区间都是合法的，答案累计 $2 \times 2^k \times (now-last_0-1) /n^2$。$now$ 是当前在枚举哪个右端点，$k$ 是当前在枚举 $a_{now}$ 的二进制第 $k$ 位。

对于 $\mathrm{or}$ 和，倘若当前数的这一位为 $1$ 则左端点在 $[1,now-1]$ 的区间都合法，否则，在 $[1,last_1]$ 间的都合法。

对于 $\mathrm{xor}$ 和，我们发现，所有的这一位数为 $1$ 的数字，把数列分成了好几段。我们记 $cnt_0$ 表示当 $a_{now}$ 的这一位是 $0$ 时有多少个左端点是能对答案产生贡献的。 $cnt_1$ 同理。

如果当前这位是 $0$，那么答案累计上 $2 \times 2^k \times cnt_0 / n^2$ 并 $cnt_0 \leftarrow cnt_0 + 1$。

如果当前这位是 $1$，那么答案累计上 $2 \times 2^k \times cnt_1 / n^2$。然后交换 $cnt_0,cnt_1$ 并 $cnt_1 \leftarrow cnt_1 + 1$。

#include <iostream>
#include <cstdio>
using namespace std;
int n, a[100005], lst0, lst1, cnt0, cnt1;
double ansand, ansxor, ansor;
int main(){
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    for(int i=0; i<=29; i++){
        lst0 = lst1 = cnt0 = cnt1 = 0;
        for(int j=1; j<=n; j++){
            int x=(a[j]>>i)&1;
            if(x){
                ansand += 1.0 * (1<<i) / n / n;
                ansxor += 1.0 * (1<<i) / n / n;
                ansor += 1.0 * (1<<i) / n / n;
                ansand += 2.0 * (j - lst0 - 1) * (1<<i) / n / n;
                ansor += 2.0 * (j - 1) * (1<<i) / n / n;
                ansxor += 2.0 * cnt1 * (1<<i) / n / n;
                swap(cnt0, cnt1);
                cnt0++;
                lst1 = j;
            }
            else{
                ansxor += 2.0 * cnt0 * (1<<i) / n / n;
                ansor += 2.0 * lst1 * (1<<i) / n / n;
                cnt1++;
                lst0 = j;
            }
        }
    }
    printf("%.3f %.3f %.3f\n", ansxor, ansand, ansor);
    return 0;
}