魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一道数学题。
S 是一个可重集合,S={a1,a2,…,an}。
等概率随机取 S 的一个子集 A={ai1,…,aim}。
计算出 A 中所有元素异或 x, 求 xk 的期望。
本文共 1517 字,大约阅读时间需要 5 分钟。
比较难的题
求出n个数的线性基,线性基中每个集合的异或和都唯一,并且属于满射
所以可以暴力线性基的所有集合异或和,然后加在一起除以2^cnt就是答案了(cnt为线性基元素个数)
但是线性基中最多有62个数,暴力是不行的
考虑按k分情况讨论
①k>=3:
因为答案不会超过long long范围,所以线性基中所有元素不会超过64/3个,可以直接暴力
不过注意一个坑:答案不会超过long long但是你计算所有异或和最后要除以2^cnt才是答案,所以计算所有贡献的过程中可能会爆long long,要边计算边除,也就是将val写成val/(2^cnt)和val%(2^cnt)两部分;
②k = 1:
不能暴力了,假设某个数ai转成二进制后第k位为1,因为这个数被选的概率刚好是1/2,并且很明显,无论它和谁异或,这个1一定都会有刚好1/2的概率对答案有贡献,所以可以发现答案就是所有数or起来/2
③k = 2:
假设某个集合的异或和为x,x转成二进制后是bm…b1b2b3(bm表示二进制第m位,0/1),那么x²就等于∑bibj*2^(i+j),当且仅当第i位第j位都为1时,对答案计算有2^(i+j)的贡献,用上面k=1的思想可以轻松得出这个概率是1/4(有00, 10, 01, 11四种情况各1/4),不过,当所有数第i位和第j位都相同时,概率会变为1/2(只有00,11两种情况),当所有数第i位都为0或者第j位都为0时概率为0
#include#define LL unsigned long longLL a[100005], p[66], jz[66], er[66] = {1};int main(void){ LL ans, temp, mod, c, d; int i, j, k, cnt, n, flag; scanf("%d%d", &n, &k); for(i=1;i<=62;i++) er[i] = er[i-1]*2; for(i=1;i<=n;i++) scanf("%llu", &a[i]); if(k==1) { ans = 0; for(i=1;i<=n;i++) ans |= a[i]; printf("%llu", ans/2); if(ans%2) printf(".5"); } else if(k==2) { temp = 0; for(i=1;i<=n;i++) temp |= a[i]; mod = ans = 0; for(i=62;i>=0;i--) { for(j=62;j>=0;j--) { if((temp&(1ll< =0;j--) { if(a[i]&(1ll<
转载地址:http://smmgf.baihongyu.com/