• 清華集訓2014 瑪里茍斯
• 求子集異或和k次方的期望。
• 異或考慮按位算貢獻。
• 對于\(K=1\)，考慮異或和\(\frac{x}{2}\)就是答案。
• 證明簡單來說就是，你可以先打一個概率\(dp\)分別對每一位來考慮。
• 假設當前考慮的位數是\(j\)，如果\(i\)這個數是\(0\)，那么選和不選的影響都是不改變原來的選取，如果\(i\)這個數是\(1\)，那么選與不選是對稱的，也就是把原來\(0\)和\(1\)的概率相互交換。
• 實際上我們在模擬一個或運算。
• 對于\(K=2\)，首先每一位如果有數，都會貢獻\(4^j\)答案。
• 如果異或和的第i位和第j為都有數，會貢獻\(2^{i+j-1}\)的答案，因為同時出現的概率是\(\frac {1}{4}\)
• 但是如果兩位不是互相獨立的，貢獻的答案應該是\(2^{i+j}\)，因為同時出現的概率是\(\frac {1}{2}\)
• \(k>=3\)，首先，線性基的定義就證明了，一個數集的異或子集，和他隨便亂異或的數集的異或子集是等效的。
• 所以可以線性基直接消掉線性相關的數。
• 由于答案在\(2^{63}\)以內，所以線性基的大小不會超過\(22\)，直接暴力枚舉計算期望。
• 這題有一個結論是答案兩倍一定是整數，也就是答案的小數最多有一位；
• \(k\leq3\)比較好證，但是\(k>3\)怎么證明啊……？？
• upd，找到證明了

#include<bits/stdc++.h> #define R register int #define db long double #define ll unsigned long long using namespace std; const int N=200001; int n,K;ll w[N]; ll gi(){ll x=0;R k=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')k=-1,c=getchar();while(c<='9'&&c>='0')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*k; } namespace cpp1{ll ans;void Main(){for(R i=1;i<=n;++i)ans|=w[i];printf("%lld",ans>>1ll);if(ans&1)cout<<".5";} } namespace cpp2{int hv[33];ll ans,res;int check(R p,R q){for(R i=1;i<=n;++i){if((w[i]&(1<<p))&&!(w[i]&(1<<q)))return 1;if((w[i]&(1<<q))&&!(w[i]&(1<<p)))return 1;}return 0;}void Main(){for(R i=1;i<=n;++i)res|=w[i];for(R i=0;i<33;++i){if((res&(1ll<<i))==0)continue;ans+=(1ll<<(i+i));for(R j=i+1;j<33;++j)if(res&(1ll<<j)){if(check(i,j))ans+=(1ll<<(i+j));else ans+=(2ll<<(i+j));}}printf("%lld",ans>>1);puts(ans&1?".5":"");} } namespace cpp3{int Mx,tot,len;ll res,num[300],now[300];__int128 ans;void ins(ll x){for(R j=0;j<Mx;++j){if((x&(1<<j))==0)continue;if(!num[j]){num[j]=x;return ;}x^=num[j];}}void Dfs(R i,ll nw){if(i==len+1){__int128 fin=1;for(R j=1;j<=K;++j)fin*=nw;ans+=fin,tot++;return ;}Dfs(i+1,nw),Dfs(i+1,nw^now[i]);}void Main(){for(R i=1;i<=n;++i){ll x=w[i];R nw=0;while(x)nw++,x>>=1;Mx=max(Mx,nw),res|=w[i];}for(R i=1;i<=n;++i)ins(w[i]);for(R i=0;i<Mx;++i)if(num[i])now[++len]=num[i];Dfs(1,0),ans>>=(len-1);ll res=ans>>1;printf("%lld",res),puts((ans&1)?".5":"");} } int main(){n=gi(),K=gi();for(R i=1;i<=n;++i)w[i]=gi();if(K==1)cpp1::Main();if(K==2)cpp2::Main();if(K>=3)cpp3::Main();return 0; }

轉載于:https://www.cnblogs.com/Tyher/p/10062176.html

總結

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

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