#概率和数学期望#JZOJ 3396 CH 3801 Rainbow的信号

题目

分析

首先位运算没有进位，这样可以让它一位一位进行，如题所述，设$x$表示$a_i$的第$k$位，当$l==r$的时候概率为$\frac{1}{n^2}$，然后当$x==1$时数学期望为$\frac{2^k}{n^2}$。
Then，当$l<r$时，概率为$\frac{2}{n^2}$，对于$and$，找到前面最后一个0的位置$t$，那么可选的$l$的个数，为$r-t-1$。
对于$or$，当$x$为1，时为任何数，否则个数为最后一个1的位置
对于$xor$,当$x$为1时就会改变个数，所以说每遇到$1$的时候个数肯定是会交换的，具体就不多解释

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
int n,a[100001]; double sxor,sand,suor;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
inline void answ(int k){rr int p0=0,p1=0,c1=0,c2=0;for (rr int i=1;i<=n;++i)if ((a[i]>>k)&1){sxor+=(1<<k)*1.0/n/n;sand+=(1<<k)*1.0/n/n;suor+=(1<<k)*1.0/n/n;sand+=(1<<k)*2.0/n/n*(i-1-p0);suor+=(1<<k)*2.0/n/n*(i-1);sxor+=(1<<k)*2.0/n/n*c1;++c1; c1^=c2,c2^=c1,c1^=c2; p1=i;}else{suor+=(1<<k)*2.0/n/n*p1;sxor+=(1<<k)*2.0/n/n*c2;++c1; p0=i;}
}
signed main(){n=iut();for (rr int i=1;i<=n;++i) a[i]=iut();for (rr int i=0;i<30;++i) answ(i);printf("%.3lf %.3lf %.3lf",sxor,sand,suor);return 0;
}