3811: 玛里苟斯

Time Limit: 10 Sec 

Memory Limit: 256 MB

Submit: 500 

Solved: 196

[ ][ ][ ]

Description

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

S 是一个可重集合，S={a1,a2,…,an}。

等概率随机取 S 的一个子集 A={ai1,…,aim}。

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

 

 

Input

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

以下 n 行每行一个整数，表示 ai。

 

 

Output

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

 

 

Sample Input

4 2

0

1

2

3

Sample Output

3.5

HINT

 

限制与约定

1≤n≤100000，1≤k≤5，ai≥0。最终答案小于 2^63 。k=1,2,3,4,5 各自占用 20% 的数据

 

 

Source

[ ][ ][ ]

 

题解：

        wwwwodddd   ORZ

       求子集异或和k次方的期望；

       首先这和期望的k次方不一样，所以还是老老实实按k分类讨论，按位算贡献吧：

       k=1 , 考虑第i位是否有1，有会贡献的$2^{i-1} $, 全部或起来除二；

       k=2，如果某个异或和的第i位和第j为都有值，会贡献$2^{i+j}$的答案 ， 首先这两位都必须要有至少一个1；

               紧接着如果对于每一个数来说，这两位的值都相同 ，说明两位不相互独立，所以概率是1/2,期望是$2^{i+j-1}$;

               否则说明两位独立，在异或运算下(0,0)(0,1)(1,0)(1,1)的概率相同为1/4，期望是$2^{i+j-2}$;

       k>=3 , 由于答案在2^63次方以内，所以线性基的大小不会超过22，直接暴力枚举计算期望；

       这题有一个结论是答案*2一定是整数；

      也就是答案的小数最多有一位；

      

这里有个评论证明了，但是我没太看懂：https://blog.sengxian.com/solutions/bzoj-3811自己给出一个可能不太严谨的证明吧（没学过数学。。。）：可以仔细分析一下k==2时的算法；再扩展到k次方，发现在异或运算下：二进制位之间贡献不相互独立是具有传递性的；假设一次计算答案时选定的k个二进制位(可能相同分)集合为：B  = {b1,b2,...bk}我们可以把他们进一步分成m个集合：S1...Sm相同集合元素贡献不互相独立，不同集合贡献互相独立；这时对答案期望的贡献应该是2^{b1+b2+...+bk - m}  ;而k >= m ， 且B里面至少有m个不同的二进制位(即bi!=bj这种)；所以考虑b1+b2+...+bk - m最小的情况：分析可以发现最小为-1；所以答案小数点后只有一位；。。。。。。

 

       这样就可以用一个数存下对2^|B|的除数和余数，分类讨论小数位的情况（建议看下代码）；

 

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include