题目描述
$\textsf {Freda}$ 发明了传呼机之后,$\textsf {rainbow}$ 进一步改进了传呼机发送信息所使用的信号。
由于现在是数字、信息时代,$\textsf {rainbow}$ 发明的信号用 $N$ 个自然数表示。
为了避免两个人的对话被大坏蛋 $\textsf {VariantF}$ 偷听,$\textsf {rainbow}$ 把对话分成 $A$、$B$、$C$ 三部分,分别用 $a$、$b$、$c$ 三个密码加密。
现在 $\textsf {Freda}$ 接到了 $\textsf {rainbow}$ 的信息,她的首要工作就是解密。
$\textsf {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}$ 和。
请你帮忙计算这三个密码。
输入格式
第一行一个正整数 $N$。
第二行 $N$ 个自然数,表示 $\textsf {Freda}$ 接到的信号。
输出格式
一行三个实数,分别表示 $\text {xor}$ 和、$\text {and}$ 和、$\text {or}$ 和的期望,四舍五入保留 $3$ 位小数,相邻两个实数之间用一个空格隔开。
数据范围
$1 \le N \le 10 ^ 5$,$N$ 个自然数均不超过 $10 ^ 9$。
输入样例:
2
4 5
输出样例:
2.750 4.250 4.750
解题思路
由于位运算是不进位的,各位之间互不影响,我们可以按位考虑 $A _ i$。我们考虑第 $k$ 位时:
我们假设 $A _ i$ 的第 $k$ 位为 $B _ i$。于是 B[i] = A[i] >> k & 1
。
按照题意,当 $l = r$ 时选出的概率为 $1 \over N ^ 2$,否则概率为 $2 \over N ^ 2$。我们可以先 $\text {O} (N)$ 扫一遍 $B$ 数组中的每一个数是否为 $1$,若为 $1$ 则累加 $2 ^ k$ 到答案中(答案最后再除以 $N ^ 2$)。
对于 $\text {xor}$ 和,我们统计 $[l, r]$ 这段区间时,先枚举右端点 $r$,左端点 $l$ 的取值如下表所示:($\sqrt {}$ 代表可取,$\times$ 代表不可取)
0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
$\times$ | $\times$ | √ | √ | √ | $\times$ | √ | $\times$ | $\times$ | $\times$ | $\times$ | √ | √ | √ | $\times$ | $r$ |
从上表中我们可以发现,若以 $1$ 为”分界点“,从右往左数第 $1, 3, 5, \ldots$ 段的长度之和为 $c _ 1$,从右往左数第 $2, 4, 6, \ldots$ 段的长度之和为 $c _ 2$,那么当 $B _ r = 1$ 时,$l$ 有 $c _ 1$ 中取值,累加 $2 ^ {k + 1} \times c _ 1$ 到答案中;当 $B _ r = 0$ 时,$l$ 有 $c _ 2$ 种取值,累加 $2 ^ {k + 1} \times c _ 2$ 到答案中。计算完后更新 $c _ 1, c _ 2$ 时,先把 $c _ 1$ 的值加上 $1$,如果 $B _ r = 1$,还需交换 $c _ 1, c _ 2$ 两个数。
对于 $\text {and}$ 和,类似地,我们设 $\text {last} _ 0$ 为 $0$ 上一次出现的位置,那么当 $B _ r = 1$ 时,$l$ 有 $r - \text {last} _ 0 - 1$ 种取值,累加 $2 ^ {k + 1} \times (r - \text {last} _ 0 - 1)$ 到答案中;当 $B _ r = 0$ 时,$l$ 有 $0$ 种取值,不累加答案。
对于 $\text {or}$ 和,类似地,我们设 $\text {last} _ 1$ 为 $1$ 上一次出现的位置,那么当 $B _ r = 1$ 时,$l$ 有 $r - 1$ 种取值,累加 $2 ^ {k + 1} \times (r - 1)$ 到答案中;当 $B _ r = 0$ 时,$l$ 有 $\text {last} _ 1$ 种取值,累加 $2 ^ {k + 1} \times \text {last} _ 1$ 到答案中。
时间复杂度
$\text O (n \log \text {MAX_INT})$
AC Code
#include <cstdio>
#define N 100005
#define swap(a,b) (a)^=(b),(b)^=(a),(a)^=(b)
using namespace std;
typedef long long ll;
int n, l0, l1, c1, c2, a[N];
long double ans1, ans2, ans3;
bool b[N];
int main ()
{
scanf ("%d", &n);
for (int i = 1; i <= n; i ++)
{
scanf ("%d", &a[i]);
}
for (int k = 0; k < 30; k ++) // 按位考虑
{
for (int i = 1; i <= n; i ++)
{
b[i] = a[i] >> k & 1; // 位运算取第 k 位
ans1 += b[i] << k, ans2 += b[i] << k, ans3 += b[i] << k;
// 顺便求出长度为 1 的区间对答案的贡献
}
l0 = l1 = c1 = c2 = 0; // 初始化
for (int i = 1; i <= n; i ++)
{
if (b[i])
{
ans1 += (1ll << k + 1) * c1;
ans2 += (1ll << k + 1) * (i - l0 - 1);
ans3 += (1ll << k + 1) * (i - 1);
}
else
{
ans1 += (1ll << k + 1) * c2;
ans3 += (1ll << k + 1) * l1;
}
(b[i] ? l1 : l0) = i, c1 ++; // 更新
if (b[i])
{
swap (c1, c2);
}
}
}
ans1 /= (ll) n * n, ans2 /= (ll) n * n, ans3 /= (ll) n * n; // 最后要除以 N * N
printf ("%.3Lf %.3Lf %.3Lf", ans1, ans2, ans3);
return 0;
}