分三種情況討論

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)內，所以我們狀壓直接暴力亂搞就好了，因為線性基的期望就是原數組的期望。然而我并不會理性證明，只能感性理解

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 #define LL unsigned long long 8 #define N 100500 9 using namespace std; 10 int n,m,p[66],bo[66]; 11 LL a[N],ANS,res; 12 vector<int> v; 13 int main(){ 14 scanf("%d%d",&n,&m); 15 for(int i=1;i<=n;i++)scanf("%llu",&a[i]); 16 if(m==1){ 17 LL ans=0; 18 for(int i=1;i<=n;i++)ans|=a[i]; 19 if(ans&1ll)printf("%llu.5\n",ans>>1ll); 20 else printf("%llu\n",ans>>1ll); 21 } 22 else if(m==2){ 23 LL ans=0; 24 for(int i=1;i<=n;i++)ans|=a[i]; 25 for(int i=0;i<=31;i++)if(ans&(1ll<<i))bo[i]=1; 26 for(int i=0;i<=31;i++)if(bo[i]){ 27 for(int j=0;j<=31;j++)if(bo[j]){ 28 bool flag=0; 29 for(int k=1;k<=n;k++)if(((a[k]>>i)&1)!=((a[k]>>j)&1)){flag=1;break;} 30 if(i+j-1-flag<0)res++; 31 else ANS+=1ll<<i+j-1-flag; 32 } 33 } 34 ANS+=res>>1ll;res&=1ll; 35 printf("%llu",ANS); 36 if(res)printf(".5\n"); 37 } 38 else{ 39 for(int i=1;i<=n;i++) 40 for(int j=23;~j;j--)if(a[i]&(1ll<<j)){ 41 if(p[j])a[i]^=a[p[j]]; 42 else{v.push_back(a[i]);p[j]=i;break;} 43 } 44 int nn=v.size(); 45 for(int i=0;i<(1<<nn);i++){ 46 LL val=0,a=0,b=1; 47 for(int j=0;j<nn;j++)if(i&(1<<j))val^=v[j]; 48 for(int j=1;j<=m;j++){ 49 a=a*val;b=b*val; 50 a+=(b>>nn);b&=(1ll<<nn)-1; 51 } 52 ANS+=a;res+=b; 53 ANS+=res>>nn;res&=(1ll<<nn)-1; 54 } 55 printf("%llu",ANS); 56 if(res)printf(".5\n"); 57 } 58 return 0; 59 } View Code

?

轉載于:https://www.cnblogs.com/Ren-Ivan/p/8379362.html

總結

以上是生活随笔為你收集整理的bzoj3811 玛里苟斯的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。