#1834. 玛里苟斯

    ID: 1834 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest178来源:qoj.ac数据:公开样例数学

玛里苟斯

玛里苟斯

题目描述

全国信息学奥林匹克竞赛 第一试 玛里苟斯 玛里苟斯 【问题描述】 魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一 道数学题。 S 是一个可重集合,S = {a1, a2, . . . , an} 等概率随机取S 的一个子集 A = {a{i1}, . . . , a{im}} 计算出A 中所有元素异或 x , 求 xk 的期望 【输入格式】 从文件malygos.in 中读入数据。 第一行两个正整数 n, k。 以下 n 行每行一个整数,表示 ai 。 【输出格式】 输出到文件malygos.out 中。 如果结果是整数,直接输出。如果结果是小数(显然这个小数是有限的),输 出精确值(末尾不加多余的0)。 【样例输入】 4 2 0 1 2 3 【样例输出】 3.5 【数据规模与约定】 1 ≤n ≤100000,1 ≤k ≤5,ai ≥0。最终答案小于263。k = 1,2,3,4,5 各自 占用 20% 的数据。 第2 页 共6 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 2
0
1
2
3
3.5