#P11713. [清华集训 2014] 玛里苟斯

[清华集训 2014] 玛里苟斯

题目描述

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

SS 是一个可重集合,S={a1,a2,,an}S = \{a_1, a_2, \dots, a_n \}

等概率随机取 SS 的一个子集 A={ai1,,aim}A = \{a_{i_1}, \dots, a_{i_m}\}

计算出 AA 中所有元素异或 xx,求 xkx^k 的期望。

输入格式

第一行两个正整数 n,kn,k

以下 nn 行每行一个整数,表示 aia_i

输出格式

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

4 2
0
1
2
3
3.5

提示

数据保证,1n1000001 \leq n \leq 1000001k51 \leq k \leq 5ai0a_i \geq 0。最终答案小于 2632^{63}k=1,2,3,4,5k = 1,2,3,4,5 各自占用 20%20\% 的数据。