题意
给定一个长度为n的序列，然后从\(1\sim N\) 这 N 个数中选取两个数\(l,r\) , 如果\(l>r\)，则交换\(l,r\)。把第\(l\) 个数到第\(r\)个数取出来构成一个数列。
A为该数列的xor和的期望
B为该数列的and和的期望
C为该数列的or和的期望
\(1\le N\le 1e5, N个自然数均不超过1e9\)
分析
- 位运算是不进位的，各位之间互不影响，因此可以把N个自然数都分成31位来单独计算
- 那些\([l,r]\) 宽度为1的，单个选取的概率其实为\(1\over {N^2}\)，而其他为\(2\over {N^2}\) 。所以可以先处理那些宽度为1的区间
ABC的具体求法：
- xor是最不好想的那个，但是看书还是比较好理解的，利用两个变量\(c_1,c_2\) 来记录从\(r-1\)倒着往前数，奇数段和偶数段的长度和（因为异或遇到1就会反转答案，所以每一段是若干个0加一个1）
- and与or是比较好求的，last0和last1分别记录最接近的0和1的位置
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int a[N];
int n;
ll nn;
double B,C,A;
void calc(int x){
int last1 = 0,last0 = 0;
int c1 = 0,c2 = 0;
double solo = 0;//区间宽度为1的
for(int i=1;i<=n;i++){
int k = a[i] >> x & 1;//k表示当前这一位是0还是1
if(k){
B += 2.0 * (i - last0 - 1) * (1 << x) / nn ;
C += 2.0 * (i - 1) * (1 << x) / nn;
A += 2.0 * c1 * (1 << x) / nn;
c1++;
swap(c1,c2);
solo += (1 << x) * 1.0 / nn;
last1 = i;
}
else{
C += 2.0 * last1 * (1 << x) / nn;
c1++;
A += 2.0 * c2 * (1 << x) / nn;
last0 = i;
}
}
B += solo;
C += solo;
A += solo;
}
int main(){
scanf("%d",&n); nn = (ll) n * n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<31;i++){
calc(i);
}
printf("%.3f %.3f %.3f\n",A,B,C);
return 0;
}