$\text{AcWing}~216$.Rainbow的信号
题目描述
Freda 发明了传呼机之后,rainbow 进一步改进了传呼机发送信息所使用的信号。
由于现在是数字、信息时代,rainbow 发明的信号用 $N$ 个自然数表示。
为了避免两个人的对话被大坏蛋 VariantF 偷听,rainbow 把对话分成 $A、B、C$ 三部分,分别用 $a、b、c$ 三个密码加密。
现在 Freda 接到了 rainbow 的信息,她的首要工作就是解密。
Freda 了解到,这三部分的密码计算方式如下:
在 $1 \sim N$ 这 $N$ 个数中,等概率地选取两个数 $l、r$,如果 $l > r$,则交换 $l、r$。
把信号中的第 l 个数到第 r 个数取出来,构成一个数列 P。
$A$ 部分对话的密码是数列 $P$ 的 $\text{xor}$ 和的数学期望值,$\text{xor}$ 和就是数列 $P$ 中各个数异或之后得到的数;$\text{xor}$ 和的期望就是对于所有可能选取的 $l、r$,所得到的数列的 $\text{xor}$ 和的平均数。
$B$ 部分对话的密码是数列 $P$ 的 $\text{and}$ 和的期望,定义类似于 $\text{xor}$ 和。
$C$ 部分对话的密码是数列 $P$ 的 $\text{or}$ 和的期望,定义类似于 $\text{xor}$ 和。
请你帮忙计算这三个密码。
思路
因为位运算当前位的结果只与当前位有关,所以可以单独考虑每一位,最后将每一位的贡献相加就是答案。
由于 $l, r$ 是等概率选取,所以 $l = r$ 的概率是 $\frac{1}{n ^ 2}$,$l \not= r$ 的概率是 $\frac{2}{n ^ 2}$。
设 $a_{i, j}$ 表示第 $i$ 个数字的第 $j$ 个二进制位的值。
接下来,我们分别考虑三种运算的期望:
$\text{and}$ 的期望
记 $pre_0$ 表示前 $x$ 个数中 $0$ 最后出现的位置。
若第 $x$ 个数字的第 $k$ 位是 $1$,以 $x$ 为右端点,在 $[pre_0 + 1, r]$ 区间内任取两个数组成的区间 $\text{and}$ 和都是 $1$,所以它的贡献为:$\begin{cases} pre_0 + 1 = x \ \ \ 2 ^ k \times \frac{1}{n ^ 2}\\\ pre_0 + 1 \not= x \ \ \ 2 ^ k \times (x - (pre_0 + 1)) \times \frac{2}{n ^ 2}\\\ \end{cases}$
若第 $x$ 个数字的第 $k$ 为是 $0$,不存在左端点与 $x$ 的组合使得区间的 $\text{and}$ 和为 $1$。
$\text{or}$ 的期望
记 $pre_1$ 表示前 $x$ 个数中 $1$ 最后出现的位置。
若第 $x$ 个数字的第 $k$ 位是 $1$,前面所有点都可以与 $x$ 组成区间使得 $\text{or}$ 和为 $1$,所以它的贡献为($l$ 表示左端点):$\begin{cases} l = x \ \ \ 2 ^ k \times \frac{1}{n ^ 2}\\\ l \not= x \ \ \ 2 ^ k \times (x - 1) \times \frac{2}{n ^ 2}\\\ \end{cases}$
若第 $x$ 个数字的第 $k$ 位是 $0$,以 $x$ 为右端点,$\le pre_1$ 的数字可以选作左端点,所以它的贡献为:$2 ^ k \times pre_1 \times \frac{2}{n ^ 2}$
$\text{xor}$ 的期望
设 $t$ 是 $[l, x]$ 区间的 $\text{xor}$ 和。从 $l = x$ 开始,将 $l$ 向左移动,若第 $l$ 位是 $1$ 则 $t$ 取反,否则 $t$ 不变。
设 $c_1$ 表示 $[l, x]$ 区间 $\text{xor}$ 和为 $0$ 的 $l$ 个数,$c_2$ 表示 $[l, x]$ 区间 $\text{xor}$ 和为 $1$ 的 $l$ 个数。
若第 $x$ 个数字的第 $k$ 位是 $1$,则 $l$ 只能选择 $c_1$ 表示的部分,所以它的贡献为:$2 ^ k \times c_1 \times \frac{2}{n ^ 2}$
若第 $x$ 个数字的第 $k$ 位是 $0$,则 $l$ 只能选择 $c_2$ 表示的部分,所以它的贡献为:$2 ^ k \times c_2 \times \frac{2}{n ^ 2}$
最后还要加上 $l = x$ 的贡献:$2 ^ k \times \frac{1}{n ^ 2}$。
我们将 $x$ 所在的位置一直看作 $c_1$ 中的位置,当 $x$ 增加 $1$,也将 $c_1$ 增加 $1$,当 $a_{x, k} = 1$,交换 $c_1, c_2$ 即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
int pre[2], c1, c2;
double resand = 0.0, resor = 0.0, resxor = 0.0;
for (int i = 0; i <= 30; i ++ )
{
pre[0] = pre[1] = 0;
c1 = c2 = 0;
for (int j = 1; j <= n; j ++ )
{
int now = (a[j] >> i) & 1;
if (now)
{
resand += 1.0 * (1 << i) / n / n + 2.0 * (1 << i) / n / n * (j - (pre[0] + 1));
resor += 1.0 * (1 << i) / n / n + 2.0 * (1 << i) / n / n * (j - 1);
resxor += 1.0 * (1 << i) / n / n + 2.0 * (1 << i) / n / n * c1;
}
else
{
resor += 2.0 * (1 << i) / n / n * pre[1];
resxor += 2.0 * (1 << i) / n / n * c2;
}
pre[now] = j;
c1 ++ ;
if (now) swap(c1, c2);
}
}
printf("%.3lf %.3lf %.3lf\n", resxor, resand, resor);
return 0;
}
$ \begin {matrix} \mathbb {tql} & \mathbf {tql} & \mathrm {tql} \\\ \mathfrak {tql} & \mathcal {tql} & \mathtt {tql} \\\ \mathsf {tql} & \mathscr {tql} & \mathit {tql} \end {matrix} \raise {5 em} {\kern {-4.3 em} \overset {巨佬} \Longrightarrow} \qquad \textsf {stO} _ {\% \% \%} ^ \mathcal {stO} \raise {5em} { \% \kern {-0.5 em} \% \kern {-0.5em} \% \texttt {stO} \left \\{ \begin {array} {} \mathbb {FXT} \\\ \text {种花家的兔兔} \\\ \mathfrak {FXT1110011010OI} \end {array} \right \\} \texttt {Orz} \% \kern {-0.5 em} \% \kern {-0.5em} \% } \kern {-16em} \mathcal {\Large {stO}} \underset {\textrm {AKIOI}} {\overset {\% \% \%} \nearrow} \kern {5.5 em} \underset {\textrm {AKIOI}} {\overset {\% \% \%} \nwarrow} \mathcal {\Large {Orz}} \kern {1em} _ {\% \% \%} ^ \mathcal {Orz} \textsf {Orz} \qquad \begin {matrix} \mathbb {tql} & \mathbf {tql} & \mathrm {tql} \\\ \mathfrak {tql} & \mathcal {tql} & \mathtt {tql} \\\ \mathsf {tql} & \mathscr {tql} & \mathit {tql} \end {matrix} \raise {5 em} {\kern {-4.3 em} \overset {巨佬} \Longleftarrow} $