题目链接:传送门
将权值转化成二进制来看,最多30位
枚举每一位并且枚举一个右端点
通过这个右端点判断有多少个左端点符合条件,累计贡献
要注意单独讨论左端点等于右端点时的情况
还有可能右端点在左端点左边,这时交换左右端点,所以下面的答案要乘二
除了左右端点重合的情况,当前的情况发生的概率是
具体的,要分情况讨论
当枚举的右端点当前这一位为时
- 对于或运算|,由于只要有一位是
就是
,当前位已经为
,所以左端点的取法有
种,就是从
取到右端点的左边一位
- 对于与运算&,只要有一个
就是
,所以我们记录上一个
出现的位置
,那么左端点可以选择的区间就是
,因为这一段区间内都是
- 对于异或运算^,可能异或偶数个
使当前值为
,还可能异或奇数个
才能使当前值为
当枚举的右端点当前这一位为时
- 对于或运算|,区间中有一个为
就可以,所以我们记上一个
出现的位置为
,由于
都为
,所以左端点可选的区间就是
- 对于与运算&,没有左端点能与起来为
- 对于异或运算^,同上讨论,累加当前数来统计异或数
#include <bits/stdc++.h>
#define
using namespace std;
int w[A], n, last[2];
double ansxor, ansor, ansand;
int main(int argc, char const *argv[]) {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
auto calc = [&](int dig) -> void {
int c1 = 0, c2 = 0; last[0] = last[1] = 0;
double val = (double)(1 << dig) / n / n;
for (int i = 1; i <= n; i++) {
int wi = (w[i] >> dig) & 1;
if (wi) ansxor += val, ansor += val, ansand += val;
if (wi) ansxor += val * c1 * 2, ansor += val * (i - 1) * 2, ansand += val * (i - last[0] - 1) * 2;
else ansxor += val * c2 * 2, ansor += val * last[1] * 2;
c1++; if (wi) swap(c1, c2);
last[wi] = i;
}
};
for (int i = 0; i <= 31; i++) calc(i);
cout << fixed << setprecision(3) << ansxor << " " << ansand << " " << ansor << endl;
}