#95. Rainbow的信号

Rainbow的信号

Freda发明了传呼机之后,rainbow进一步改进了传呼机发送信息所使用的信号。

由于现在是数字、信息时代,rainbow发明的信号用N个自然数表示。

为了避免两个人的对话被大坏蛋VariantF偷听,rainbow把对话分成A、B、C三部分,分别用a、b、c三个密码加密。

现在Freda接到了rainbow的信息,她的首要工作就是解密。

Freda了解到,这三部分的密码计算方式如下:

在1~N这N个数中,等概率地选取两个数l、r,如果l>r,则交换l、r。把信号中的第l个数到第r个数取出来,构成一个数列P。

A部分对话的密码是数列P的xor和的数学期望值,xor和就是数列P中各个数异或之后得到的数; xor和的期望就是对于所有可能选取的l、r,所得到的数列的xor和的平均数。

B部分对话的密码是数列P的and和的期望,定义类似于xor和。

C部分对话的密码是数列P的or和的期望,定义类似于xor和。

请你帮忙计算这三个密码。

输入格式

第一行一个正整数N。

第二行N个自然数,表示Freda接到的信号。

输出格式

一行三个实数,分别表示xor和、and和、or和的期望,四舍五入保留3位小数,相邻两个实数之间用一个空格隔开。

数据范围

1N1051 \le N \le 10^5,N个自然数均不超过10910^9

输入样例:

2
4 5

输出样例:

2.750 4.250 4.750

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解