欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1006. -- 亮亮破解密码

1006: 亮亮破解密码

时间限制: 2 Sec  内存限制: 128 MB
提交: 83  解决: 19
[提交][状态][讨论版]

题目描述

小W为了防止亮亮拿他的电脑打Loly of Lord(LoL),给电脑设置了密码。而亮亮是一位非常高富帅的苹果用户,不屑于在自己的Macbook上装Windows,又不敢用实验室流量装Wine,就没法拿自己的电脑打LOL。因此,他用尽各种办法试图破解小W的密码。一天,小W打Coding Flood(CF)比赛时AK了,心情很好,就给了亮亮一个很长的数列A={a1,a2,...,aN},并告诉他:自己的Windows密码由三部分组成,每部分都能由这个数列得到。密码的计算方式如下:

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

第一部分的密码是数列P中所有数按位异或(^)操作后得到的数的数学期望。
第二部分的密码是数列P中所有数按位与(&)操作后得到的数的数学期望。
第三部分的密码是数列P中所有数按位或(|)操作后得到的数的数学期望。

请你帮助亮亮求出这三部分密码。小W透露,他的密码在小数点后保留了3位。

输入

输入包含多组数据,请处理到EOF。
每组数据,第一行,一个整数N。第二行,N个整数a1,a2,...,aN。
对于100%的数据,1<=N<=100000,0<=ai<230

输出

对于每组测试数据,输出一行,包含三个实数,用空格分割,表示三部分的密码。

样例输入

2
4 5
3
1 0 1

样例输出

2.750 4.250 4.750
0.667 0.222 0.889

提示

样例1共包含4种可能的(l,r):

l,r   xor   and    or

1,1    4     4     4

1,2    1     4     5

2,1    1     4     5

2,2    5     5     5

以上每一对(l,r)出现的概率相同,故对它们取平均数就是数学期望。

来源

[提交][状态][讨论版]