题解 | Rainbow的信号

选取的概率为，选取的概率为
分别考虑三种运算并按位考虑，考虑第位：
对于的情况显然贡献为，为第位为的数的个数。（三种运算的情况都一样）
对于和，记录前面连续的个数，那么当前位置作为右端点，对期望的贡献为
对于和，记录前面第一个有的位置，那么当前位置作为右端点，对期望的贡献为
对于和，记录前缀和，并维护和两个桶。当当前为时，对期望的贡献为；当当前为时，对期望的贡献为。
这题有点卡精度...要用long double并将除法运算挪到适当的位置...

#include <bits/stdc++.h>
using namespace std;
#define double long double
const int N = 100010;

double ans;
int a[N], n, s[N], cnt[2];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    ans = 0;
    for(int k = 30; k >= 0; --k) {
        memset(s, 0, sizeof(s));
        cnt[0] = cnt[1] = 0;
        for(int i = 1; i <= n; ++i) {
            if((a[i] >> k) & 1) s[i] = s[i - 1] ^ 1;
            else s[i] = s[i - 1];
            if((a[i] >> k) & 1) ans += (double) (1 << k) / n / n;
        }
        for(int i = 1; i <= n; ++i) {
            ans += (double)(1 << k)  / n / n * cnt[s[i] ^ 1] * 2;
            cnt[s[i - 1]]++;
        }
    }
    printf("%.3Lf ", ans);
    ans = 0;
    for(int k = 30; k >= 0; --k) {
        memset(s, 0, sizeof(s));
        for(int i = 1; i <= n; ++i) {
            if((a[i] >> k) & 1) s[i] = s[i - 1] + 1;
            else s[i] = 0;
            if((a[i] >> k) & 1) ans += (double) (1 << k) / n / n;
        }
        for(int i = 1; i <= n; ++i)
            if((a[i] >> k) & 1) ans += (double)(1 << k)  / n / n * s[i - 1] * 2;
    }
    printf("%.3Lf ", ans);
    ans = 0;
    for(int k = 30; k >= 0; --k) {
        memset(s, 0, sizeof(s));
        for(int i = 1; i <= n; ++i) {
            if((a[i] >> k) & 1) s[i] = i;
            else s[i] = s[i - 1];
            if((a[i] >> k) & 1) ans += (double) (1 << k) / n / n;
        }
        for(int i = 1; i <= n; ++i) {
            if((a[i] >> k) & 1) ans += (double)(1 << k) / n / n * (i - 1) * 2;
            else ans += (double)(1 << k) / n / n * s[i] * 2;
        }
    }
    printf("%.3Lf\n", ans);
}