AcWing 216. Rainbow的信号

题目链接：​​传送门​​

将权值转化成二进制来看，最多30位
枚举每一位并且枚举一个右端点
通过这个右端点判断有多少个左端点符合条件，累计贡献
要注意单独讨论左端点等于右端点时的情况
还有可能右端点在左端点左边，这时交换左右端点，所以下面的答案要乘二
除了左右端点重合的情况，当前的情况发生的概率是
具体的，要分情况讨论
当枚举的右端点当前这一位为时

1. 对于或运算|，由于只要有一位是就是，当前位已经为，所以左端点的取法有种，就是从取到右端点的左边一位
2. 对于与运算&，只要有一个就是，所以我们记录上一个出现的位置，那么左端点可以选择的区间就是，因为这一段区间内都是
3. 对于异或运算^，可能异或偶数个使当前值为，还可能异或奇数个才能使当前值为

当枚举的右端点当前这一位为时

1. 对于或运算|，区间中有一个为就可以，所以我们记上一个出现的位置为，由于都为，所以左端点可选的区间就是
2. 对于与运算&，没有左端点能与起来为
3. 对于异或运算^，同上讨论，累加当前数来统计异或数

#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;
}