主要思路

这道题挺有趣的，归根结底就是位运算。首先，一个充分的结论就是枚举长度为\(1\)的区间的概率为\(\frac{1}{N^2}\)，而长度大于1的概率为\(\frac{2}{N^2}\)。之后，枚举\(int\)的长度\(i \in [0,30]\)，把所有数的第\(i\)位组成一个序列进行扫描，之后枚举到第\(j\)个数进行分类讨论。

• 如果运算符是\(and\)，那么我们记\(last[0]\)为最后一个\(0\)的位置，中间一共有\(k-last[0]+1\)个与之运算得到1的数。乘上概率更新答案。
• 如果运算符是\(or\)，那么区间概率直接乘上\(i-1\)即可。
• 如果运算符是\(xor\)，我们需要把之前的\(0,1\)进行分块，记\(c_1,c_2\)为前面区间长的和，且\(c_1\)与\(c_2\)的区间不重合，交替进行。每次乘上相应的块长度即可，对于\(1\)进行块交换，\(0\)则保持原样。

代码

// CH3801.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, arr[MAX_N];
double ans1, ans2, ans3;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for (int k = 0; k < 30; k++)
    {
        int last[2], c1 = 0, c2 = 0;
        last[0] = last[1] = 0;
        for (int i = 1; i <= n; i++)
            if ((arr[i] >> k) & 1)
            {
                ans1 += (1 << k) * 1.0 / n / n;
                ans2 += (1 << k) * 1.0 / n / n;
                ans3 += (1 << k) * 1.0 / n / n;
                ans1 += (1 << k) * 2.0 / n / n * c1;
                ans2 += (1 << k) * 2.0 / n / n * (i - 1);
                ans3 += (1 << k) * 2.0 / n / n * (i - 1 - last[0]);
                last[1] = i;
                c1++, swap(c1, c2);
            }
            else
            {
                ans1 += (1 << k) * 2.0 / n / n * c2;
                ans2 += (1 << k) * 2.0 / n / n * (last[1]);
                last[0] = i, c1++;
            }
    }
    printf("%.3lf %.3lf %.3lf", ans1, ans3, ans2);
    return 0;
}