#1168. QOJ 178_6

    ID: 1168 传统题 1000ms 256MiB 尝试: 1 已通过: 0 难度: 省选/NOI- 上传者: 标签>QOJ来源:qoj.ac 178_6答案:本地AC标程生成数学

QOJ 178_6

QOJ 178_6

题目描述

全国信息学奥林匹克竞赛 第一试 玛里苟斯 玛里苟斯 【问题描述】 魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一 道数学题。 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 46
1
2
3
3
1
4
1
3
3
1
3
1
4
1
4
4
4
2
2
2
2
2
3
1
1
1
3
3
1
1
4
4
1
3
1
2
2
2
2
3
1
2
3
1
2125258660165124478.5