题目：
Freda发明了传呼机之后，rainbow进一步改进了传呼机发送信息所使用的信号。由于现在是数字、信息时代，rainbow发明的信号用N个自然数表示。为了避免两个人的对话被大坏蛋VariantF偷听T_T，rainbow把对话分成A、B、C三部分，分别用a、b、c三个密码加密。现在Freda接到了rainbow的信息，她的首要工作就是解密。Freda了解到，这三部分的密码计算方式如下：
在1~N这N个数中，等概率地选取两个数l、r，如果l>r，则交换l、r。把信号中的第l个数到第r个数取出来，构成一个数列P。
A部分对话的密码是数列P的xor和的数学期望值。xor和就是数列P中各个数异或之后得到的数； xor和的期望就是对于所有可能选取的l、r，所得到的数列的xor和的平均数。
B部分对话的密码是数列P的and和的期望，定义类似于xor和。
C部分对话的密码是数列P的or和的期望，定义类似于xor和。
分析：
（如果你想AC的话，请忽略此部分）
这个题的暴力其实很好打，直接进行无脑循环：（复杂度O(n^2)已经是优化过的了）
40分代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long n; long long a[100010]; long long Xor[5000][5000],And[5000][5000],Or[5000][5000]; double ans1=0,ans2=0,ans3=0; long long cnt=0; long long read() { long long ret=0,flag=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-') flag=-1; ch=getchar(); } while(ch>='0' && ch<='9') { ret=ret*10+(long long)(ch-'0'); ch=getchar(); } return ret*flag; } int main() { n=read(); cnt=n*n; for(int i=1;i<=n;i++) a[i]=read(); memset(Xor,0,sizeof(Xor)); memset(And,0,sizeof(And)); memset(Or,0,sizeof(Or)); for(int i=1;i<=n;i++) { Xor[i][i]=a[i]; ans1+=Xor[i][i]; And[i][i]=a[i]; ans2+=And[i][i]; Or[i][i]=a[i]; ans3+=Or[i][i]; } for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) { int p=(i+j)/2; Xor[i][j]=Xor[i][p]^Xor[p+1][j]; ans1+=Xor[i][j]*2; } for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) { int p=(i+j)/2; And[i][j]=And[i][p]&And[p+1][j]; ans2+=And[i][j]*2; } for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) { int p=(i+j)/2; Or[i][j]=Or[i][p]|Or[p+1][j]; ans3+=Or[i][j]*2; } printf("%.3lf %.3lf %.3lf ",ans1/cnt,ans2/cnt,ans3/cnt); return 0; }
而正解其实也不远了，通过分析这三种运算符的特点，只关心1的贡献：
(^):
1^1=0;
0^1=1;
他的功能就是：只要遇到1，就把当前的异或和取反，因此只要遇到1，就交换之前1和0的个数（即所有的1都变成了0，所有的0都变成了1）并且给1的个数加1；（自己应当拿笔模拟一下）
(&):
1&1=1；
1&0=0；
他的功能就是：只要遇到0，后面的都是0，因此只要找到前一个0出现的位置作为断点，计算有多少1出现就行了；
(|):
1|0=1；
1|1=1；
他的功能就是：只要遇到1，后面的都是1，因此只要找到前一个1出现的位置作为断点，计算有多少1出现就行了；
下面是参考代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; int n; int cnt[2],last_pos[2]; int a[100005],b[100005]; double ans_or=0,ans_xor=0,ans_and=0; void cal(int x) { fill(cnt,cnt+2,0); fill(last_pos,last_pos+2,0); for(int i=1;i<=n;i++) b[i]=((a[i]>>x)&1); for(int i=1;i<=n;i++) { if(i!=1) { ans_xor+=(double)(1<<x)/n/n*cnt[!b[i]]; if (b[i]==0) ans_or+=(double)(1<<x)/n/n*last_pos[1]; else { ans_or+=(double)(1<<x)/n/n*(i-1); ans_and+=(double)(1<<x)/n/n*(i-1-last_pos[0]); } } last_pos[b[i]]=i; if(b[i]==0) cnt[0]++; else swap(cnt[0],cnt[1]),cnt[1]++; } for(int i=1;i<=n;i++) if(b[i]) { double tmp=(double)(1<<x)/n/n/2; ans_xor+=tmp; ans_or+=tmp; ans_and+=tmp; } } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<=30;i++) cal(i); printf("%.3lf %.3lf %.3lf",ans_xor*2,ans_and*2,ans_or*2); return 0; }