UOJ Logo Universal Online Judge

UOJ

#36. 【清华集训2014】玛里苟斯

统计

魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一道数学题。

$S$ 是一个可重集合,$S = \{a_1, a_2, \dots, a_n \}$。

等概率随机取 $S$ 的一个子集 $A = \{a_{i_1}, \dots, a_{i_m}\}$。

计算出 $A$ 中所有元素异或 $x$, 求 $x^k$ 的期望。

输入格式

第一行两个正整数 $n$, $k$。

以下 $n$ 行每行一个整数,表示 $a_i$。

输出格式

如果结果是整数,直接输出。如果结果是小数(显然这个小数是有限的),输出精确值(末尾不加多余的 $0$)。

样例一

input

4 2
0
1
2
3

output

3.5

限制与约定

$1 \leq n \leq 100000$,$1 \leq k \leq 5$,$a_i \geq 0$。最终答案小于 $2^{63}$ 。$k = 1,2,3,4,5$ 各自占用 20% 的数据。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

来源

中国国家队清华集训2014~2015 Day 1 - By 毕克

下载

样例数据下载