【BZOJ3811】瑪里茍斯（線性基）

題面

BZOJ

題解

\(K=1\)很容易吧，拆位考慮貢獻，所有存在的位出現的概率都是\(0.5\)，所以答案就是所有數或起來的結果除二。
\(K=2\)的情況，我們直接拆開平方式，平方項的貢獻直接算，出現的概率還是\(0.5\)，然后\(2ab\)這樣子的東西出現的概率是\(0.5*0.5=0.25\)，然而注意到有一些位直接兩兩之間存在聯系，即選擇了第\(i\)位的時候必定會同時選擇第\(j\)位，那么此時兩位之間的概率就是\(0.5\)，這一部分要特殊判斷一下。
接下來考慮\(K\ge 3\)的情況。因為答案不會超過\(2^{63}\)，所以任何一個數字都不會從超過\(2^{22}\)。我們知道如果一個數可以被線性基中的其他所有數給表示出來，那么這個數出現的概率一定是\(1/{2^{|G|}}\)，其中\(|G|\)是線性基內的元素個數。既然數字大小不大，那么線性基中的元素個數也不多，所以可以構建線性基之后直接\(2^{|G|}\)枚舉所有可能出現的數字，\(K\)次方之后求和即可。
注意一下，最終答案除掉總的數字個數之后在\(2^{63}\)以內，那么在除之前是可能爆掉的，所以這里可以拆位什么的存一下就好了。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define ll long long #define ull unsigned long long inline ull read() {ull x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,K;ull a[100100]; namespace Task1 {void Solve(){ull ans=0;for(int i=1;i<=n;++i)ans|=a[i];if(ans&1)printf("%llu.5\n",ans>>1);else printf("%llu\n",ans>>1);} } namespace Task2 {bool vis[50];bool check(int x,int y){if(!vis[x]||!vis[y])return false;for(int i=1;i<=n;++i){if((a[i]&(1ll<<x))&&!(a[i]&(1ll<<y)))return false;if((a[i]&(1ll<<y))&&!(a[i]&(1ll<<x)))return false;}return true;}void Solve(){ull ans=0;for(int i=0;i<33;++i)for(int j=1;j<=n;++j)if(a[j]&(1ll<<i)){vis[i]=true;break;}for(int i=0;i<33;++i)if(vis[i])ans+=1ll<<(i+i);for(int i=0;i<33;++i)for(int j=i+1;j<33;++j)if(vis[i]&&vis[j])ans+=1ll<<(i+j);for(int i=0;i<33;++i)for(int j=i+1;j<33;++j)if(check(i,j))ans+=1ll<<(i+j);if(ans&1)printf("%llu.5\n",ans>>1);else printf("%llu\n",ans>>1);} } namespace Task3 {int p[50];void insert(int x){for(int i=30;~i;--i)if(x&(1<<i)){if(!p[i]){p[i]=x;return;}x^=p[i];}}int S[55],top;ull ans=0,r=0;void Calc(int val){int MOD=1<<top;ull D=0,R=1;for(int i=1;i<=K;++i){D*=val;R*=val;D+=R/MOD;R%=MOD;}ans+=D;r+=R;ans+=r/MOD;r%=MOD;}void dfs(int x,int val){if(x==top+1){Calc(val);return;}dfs(x+1,val);dfs(x+1,val^S[x]);}void Solve(){for(int i=1;i<=n;++i)insert(a[i]);for(int i=0;i<=30;++i)if(p[i])S[++top]=p[i];dfs(1,0);if(r)printf("%llu.5\n",ans);else printf("%llu\n",ans);return;} } int main() {n=read(),K=read();for(int i=1;i<=n;++i)a[i]=read();if(K==1){Task1::Solve();return 0;}if(K==2){Task2::Solve();return 0;}if(K>=3){Task3::Solve();return 0;}return 0; }

轉載于:https://www.cnblogs.com/cjyyb/p/10056615.html

總結

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

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