首先有一些前置引理：
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} imes 2^x$，直接做即可。
当k=2时，将异或和每一位拆开来分情况讨论，这部分是较为复杂的。
基本上就像下面这样。
http://www.cnblogs.com/Blue233333/p/8930885.html
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 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; 28 } 29 printf("%llu",(ull)(ans/2)); 30 if (ans&1) printf(".5"); 31 } 32 33 void solve2(){ 34 ull ans=0,res=0; 35 for (int i=0;i<=31;i++) 36 for (int j=0;j<=31;j++){ 37 bool c1,c2,c3,c4; c1=c2=c3=c4=0; 38 for (int k=0;k<=31;k++){ 39 if (((b.a[k]>>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 else 48 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<<lp);i++){ 58 ull now=0,x=0,y=1; 59 for (int j=0;j<lp;j++) if ((i>>j)&1) now^=p[j]; 60 for (int j=0;j<K;j++) 61 x*=now,y*=now,x+=y>>lp,y=y&((1<<lp)-1); 62 res+=y; ans+=x; 63 } 64 printf("%llu",ans+(res>>lp)); 65 if (res&((1<<lp)-1)) printf(".5"); 66 } 67 68 int main(){ 69 freopen("bzoj3811.in","r",stdin); 70 freopen("bzoj3811.out","w",stdout); 71 scanf("%d%d",&n,&K); 72 for (int i=1;i<=n;i++) scanf("%llu",&x),b.insert(x); 73 if (K==1) solve1(); 74 else if (K==2) solve2(); else solve3(); 75 return 0; 76 } 77 78 bzoj3811