bzoj#P3054. Rainbow的信号

Rainbow的信号

题目描述

Freda 发明了传呼机之后,rainbow 进一步改进了传呼机发送信息所使用的信号。由于现在是数字、信息时代,rainbow 发明的信号用 NN 个自然数表示。为了避免两个人的对话被大坏蛋 VariantF 偷听,rainbow 把对话分成 A,B,CA,B,C 三部分,分别用 a,b,ca,b,c 三个密码加密。

现在 Freda 接到了 rainbow 的信息,她的首要工作就是解密。Freda 了解到,这三部分的密码计算方式如下:

1N1\sim NNN 个数中,等概率地选取两个数 l,rl,r,如果 l>rl>r,则交换 l,rl,r。把信号中的第 ll 个数到第 rr 个数取出来,构成一个数列 PP

AA 部分对话的密码是数列 PPxor{\rm xor} 和的数学期望值。xor\rm xor 和就是数列 PP 中各个数异或之后得到的数; xor\rm xor 和的期望就是对于所有可能选取的 l,rl,r,所得到的数列的 xorxor 和的平均数。 BB 部分对话的密码是数列 PPand\rm and 和的期望,定义类似于 xor\rm xor 和。 CC 部分对话的密码是数列 PPor\rm or 和的期望,定义类似于 xor\rm xor 和。

输入格式

第一行一个正整数 NN。 第二行 NN 个自然数,表示 Freda 接到的信号。

输出格式

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

2
4 5
2.750 4.250 4.750
3
1 0 1
0.667 0.222 0.889

提示

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

题目来源

Poetize9