#P3811. 玛里苟斯

    ID: 3013 传统题 3000ms 256MiB 尝试: 767 已通过: 212 难度: 8 上传者: 标签>CF2400提高+/省选-线性基全子集枚举期望线性性按位独立贡献高精度加法高精度乘法高精度除法

玛里苟斯

题目描述

给定序列 a1⋯na_{1\cdots n},求它的子序列 ap1⋯pma_{p_1\cdots p_m} 的 (⨁i=1mapi)k(\bigoplus_{i=1}^m a_{p_i})^k 的期望值,其中 ⨁\bigoplus 是异或符号。

输入格式

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

接下来 nn 行,第 i+1i+1 行一个整数表示 aia_i。

输出格式

若答案是整数,直接输出。

否则答案一定是一个有限小数,输出答案的精确值,末尾不添加额外的 00。

4 2
0
1
2
3
3.5

数据规模与约定

对于 100%100\% 的数据,1≤n≤1051\leq n\leq 10^5,1≤k≤51\leq k\leq 5,ai≥0a_i\ge 0,最终答案小于 2632^{63}。

对于 k=1,2,3,4,5k=1,2,3,4,5,各自存在 20%20\% 的数据。

来源

20152015 年国家集训队测试。