bzoj3811 玛里苟斯

分三种情况讨论

k=1时，对于每一位而言，只要有一个数这一位是1，那么这个就有0.5的概率是1，选他就是1，不选就是0，有第二个的话，在第一个选或不选的前提下，也各有0.5的几率选或不选，0和1的概率还是一半一半。所以无论有几个，只要有任意一个数该位不得0，期望就是(1<<i)/2。所以我们只需要把所有的或起来除以二即可。

k=2时，我们需要记录每两位之间的贡献，如果所有的数这两位都一样而且有都是1的数，那么这两位作出的贡献就是(1<<i+j)/2，

如果有不一样的，那么贡献就是(1<<i+j)/4，

k>=3时，我们发现现在的异或和最大是(1<<22)，因为题目保证答案在(1<<63)内，所以我们状压直接暴力乱搞就好了，因为线性基的期望就是原数组的期望。然而我并不会理性证明，只能感性理解

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #define LL unsigned long long

 #define N 100500

 using namespace std;

 int n,m,p[],bo[];

 LL a[N],ANS,res;

 vector<int> v;

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)scanf("%llu",&a[i]);

     if(m==){

         LL ans=;

         for(int i=;i<=n;i++)ans|=a[i];

         if(ans&1ll)printf("%llu.5\n",ans>>1ll);

         else printf("%llu\n",ans>>1ll);

     }

     else if(m==){

         LL ans=;

         for(int i=;i<=n;i++)ans|=a[i];

         for(int i=;i<=;i++)if(ans&(1ll<<i))bo[i]=;

         for(int i=;i<=;i++)if(bo[i]){

             for(int j=;j<=;j++)if(bo[j]){

                 bool flag=;

                 for(int k=;k<=n;k++)if(((a[k]>>i)&)!=((a[k]>>j)&)){flag=;break;}

                 if(i+j--flag<)res++;

                 else ANS+=1ll<<i+j--flag;

             }

         }

         ANS+=res>>1ll;res&=1ll;

         printf("%llu",ANS);

         if(res)printf(".5\n");

     }

     else{

         for(int i=;i<=n;i++)

             for(int j=;~j;j--)if(a[i]&(1ll<<j)){

                 if(p[j])a[i]^=a[p[j]];

                 else{v.push_back(a[i]);p[j]=i;break;}

             }

         int nn=v.size();

         for(int i=;i<(<<nn);i++){

             LL val=,a=,b=;

             for(int j=;j<nn;j++)if(i&(<<j))val^=v[j];

             for(int j=;j<=m;j++){

                 a=a*val;b=b*val;

                 a+=(b>>nn);b&=(1ll<<nn)-;

             }

             ANS+=a;res+=b;

             ANS+=res>>nn;res&=(1ll<<nn)-;

         }

         printf("%llu",ANS);

         if(res)printf(".5\n");

     }

     return ;

 }