Acwing216. Rainbow的信号 【期望+位运算】

网上好多异或都用的奇期间，偶区间来处理的。
我是用的计数异或前缀和为0和为1的个数来处理的，比较好理解。但是要注意到前缀可以为空，多一个什么也不选，异或为0的前缀

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>

#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e5+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------
int N;
int a[maxn],w[maxn],pre_xor[maxn];
double ans_and = 0,ans_or = 0,ans_xor = 0;
void solve(int k){
    int last0 = 0,last1 = 0;
    int cnt0 = 0,cnt1 = 0;
    memset(w,0,sizeof w);
    memset(pre_xor, 0, sizeof pre_xor);
    go(i,1,N){
        w[i] =(int)((a[i]>>k)&1);
        if(w[i]){
            double e = (1<<k) * (double)1 /N/N; //区间长度为1
            ans_and += e;
            ans_or += e;
            ans_xor += e;
        }
        pre_xor[i] = w[i] ^ pre_xor[i - 1];
    }
    go(i,1,N){
        if(w[i]){
            ans_or += (1<<k) * (double)2/N/N * (i-1);
            ans_and += (1<<k) * (double)2/N/N * (i - last0-1);
        }else{
            ans_or += (1<<k) * (double)2/N/N * (last1);
        }
        if(w[i]) last1 = i;else last0 = i;
    }

    for(int i = 0;i<=N;i++){ //异或长度>=2的处理
        if(pre_xor[i] == 0) cnt0 ++; else cnt1++;
        if(i+2<=N){
            if(pre_xor[i + 2]){
                ans_xor += (1<<k) *(double)2/N/N * cnt0;
            }else{
                ans_xor += (1<<k) *(double)2/N/N * cnt1;
            }
        }
    }
}
int main() {
//    debug_in;
//    debug_out;

    read(N);
    for(int i = 1;i<=N;i++) read(a[i]);
    go(i,0,31){
        solve(i);
    }
    printf("%.3f %.3f %.3f\n",ans_xor,ans_and,ans_or);

    return 0;
}