Nescafe 26 Rainbow 的信号
(signal.pas/c/cpp) 题目描述 Freda 发明了传呼机之后，rainbow 进一步改进了传呼机发送信息所使用的信号。由于 现在是数字、信息时代，rainbow发明的信号用 N个自然数表示。为了避免两个人的对话被 大坏蛋 VariantF偷听 T_T，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和的平均数。 A部分对话占接收到的信息总量的 40%，因此如果你计算出密码 a， 将获得该测试点40% 的分数。 B部分对话的密码是数列 P的 and和的期望，定义类似于 xor和，占信息总量的 30%。 C部分对话的密码是数列 P的 or和的期望，定义类似于 xor和，占信息总量的 30%。 输入格式 第一行一个正整数 N。 第二行 N个自然数，表示 Freda接到的信号。 输出格式 一行三个实数，分别表示 xor和、and和、or和的期望，四舍五入保留 3位小数，相邻 两个实数之间用不少于一个空格隔开。三个实数分别占该测试点 40%、30%、30%的分数， 如果你的输出少于三个实数，或者你的输出不合法，将被判 0分。 样例输入 1 2 4 5 样例输出 1 2.750 4.250 4.750 样例输入 2 3 Nescafe 26 1 0 1 样例输出 2 0.667 0.222 0.889 样例解释 样例 1共包含四种可能的 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出现的概率均相同，因此分别对 xor和、and和、or和取平均数就是数 学期望值。 数据范围与约定 对于 20%的数据，1<=N<=100。 对于 40%的数据，1<=N<=1000。 对于另外 30%的数据，N个数为 0或 1。 对于 100%的数据，1<=N<=100000，N个自然数均不超过 10^9。