首先有一些前置引理：

1. 由期望的线性性，平方的期望不等于期望的平方，所以求k次方的期望时，需要记录1~k-1的期望，然后计算增量（OSU！），这个这题没用上。

2. 线性基是可以变成每位只在一个元素上为1的（rebuild操作，也是求张成空间第k大的做法）。有一个关键的结论，张成空间内所有元素（设为k个）的出现概率都为$\frac{1}{2^k}$，也就是所有可能出现的异或和都是等概率的。

3. n个球里随机选，选到奇数个的概率和偶数个的概率各为1/2。观察杨辉三角可发现，偶数行由于对称显然成立，奇数行根据上一行得到所以也成立。（显然n=1除外）。

然后这题就可以做了。

首先k>=3时，可以知道x<=2^21，也就是张成空间最大为2^21，这个可以直接暴力搜索所有元素统计。

这里可能会爆unsigned long long，根据引理二发现分母是固定的，所以我们只要维护一个带分数（即一个整数和一个小于分母的分子）即可。

最后答案一定要么是整数，要么是.5。

当k=1时，根据引理三可知，如果有一位上所有数均为0，则这一位贡献为0，否则贡献为$\frac{1}{2}\times 2^x$，直接做即可。

当k=2时，将异或和每一位拆开来分情况讨论，这部分是较为复杂的。

基本上就像下面这样。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define rep(i,l,r) for (int i=l; i<=r; i++) 5 typedef unsigned long long ull; 6 using namespace std; 7  8 const int N=200010; 9 int n,K,lp;10 ull p[66],x;11 12 struct P{13     ull a[66]; int n;14     void insert(ull v){15         for (int i=63;~i && v;i--) if ((v>>i)&1){16             if (!a[i]) {a[i]=v; n++; break;}17             v^=a[i];18         }19     }20 }b;21 22 void solve1(){23     ull ans=0;24     for (int i=0;i<=63;i++){25         bool flag=0;26         for (int j=0;j<=63;j++) if ((b.a[j]>>i)&1) flag=1;27         if (flag) ans+=1ll<
        
         >i)&1)==1 && ((b.a[k]>>j)&1)==1) c1=1;40                 if (((b.a[k]>>i)&1)==1 && ((b.a[k]>>j)&1)==0) c2=1;41                 if (((b.a[k]>>i)&1)==0 && ((b.a[k]>>j)&1)==1) c3=1;42                 if (((b.a[k]>>i)&1)==0 && ((b.a[k]>>j)&1)==0) c4=1;43             }44             if (!(c1 || c3) || !(c1 || c2)) continue;45             if (!(c3 || c2))46                 if (i+j>0) ans+=(1ll<<(i+j-1)); else res+=2;47             else48                 if (i+j>1) ans+=(1ll<<(i+j-2)); else res+=(1<<(i+j));49         }50     printf("%llu",ans+(res>>2));51     if (res&3) printf(".5");52 }53 54 void solve3(){55     for (int i=0;i<=63;i++) if (b.a[i]) p[lp++]=b.a[i];56     ull ans=0,res=0;57     for (int i=0;i<(1<
         
          >j)&1) now^=p[j];60         for (int j=0;j
          
           >lp,y=y&((1<
           
            >lp));65 if (res&((1<