BZOJ3811: 瑪里茍斯

https://lydsy.com/JudgeOnline/problem.php?id=3811

分析:

• \(K=1\)可以隨便做，每一位的貢獻都是確定的，推一推可以發現每一位是\(1\)的概率都是\(1/2\)，這是因為這位是\(0\)的數字對答案沒有影響。直接把所有數或起來除\(2\)就可以。
• \(K>2\)的情況最多有\(21\)位數字，我們感性理解一下可知所有能異或出來的數字的概率相同，建出線性基暴力枚舉異或出的數字是什么即可。
• \(K=2\)的情況需要推一推式子，這里有一篇很好的題解http://www.cnblogs.com/wangck/p/4187488.html

代碼:

#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; typedef long long ll; typedef unsigned long long ull; #define N 100050 int n,K; ull a[N]; namespace Cas1 {int main() {ull ans=0;int i;for(i=1;i<=n;i++) ans|=a[i];printf("%llu",ans>>1);if(ans&1) printf(".5");puts("");return 0;} } namespace Cas2 {int main() {ull mx=0,ans=0,re=0;int i,j,k;for(i=1;i<=n;i++) mx|=a[i];for(i=62;i>=0;i--) {for(j=62;j>=0;j--) {if(!(mx>>i&1)||!(mx>>j&1)) continue;int flg=1;for(k=1;k<=n;k++) {if(((a[k]>>i)&1)!=((a[k]>>j)&1)) {flg=0; break;}}if(flg) ans+=(1llu<<(i+j))/2,re+=(1llu<<(i+j))&1;else ans+=(1llu<<(i+j))/4,re+=(1llu<<(i+j))%4>0;}}printf("%llu",ans+re/2);if(re&1) printf(".5"); puts("");return 0;} } namespace Cas3 {ull b[100],c[100],ans,re;int m;void insert(ull x) {int i;for(i=22;i>=0;i--) if((x>>i)&1) {if(b[i]) x^=b[i];else {b[i]=x; return ;}}}int main() {int i,s;for(i=1;i<=n;i++) insert(a[i]);for(i=22;i>=0;i--) if(b[i]) c[++m]=b[i];int mask=(1<<m)-1;for(s=0;s<=mask;s++) {ull val=0;for(i=1;i<=m;i++) if(s&(1<<(i-1))) val^=c[i];ull a=0,b=1;for(i=1;i<=K;i++) {a=a*val; b=b*val;a+=b>>m; b&=mask;}ans+=a;re+=b;ans+=re>>m;re&=mask;}printf("%llu",ans);if(re) printf(".5");puts("");return 0;} } int main() {scanf("%d%d",&n,&K);int i;for(i=1;i<=n;i++) {scanf("%llu",&a[i]);}if(K==1) {return Cas1::main();}else if(K==2) {return Cas2::main();}else {return Cas3::main();} }

轉載于:https://www.cnblogs.com/suika/p/10264093.html

總結

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

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