[BZOJ 3811]玛里苟斯：线性基（详细证明）

本文主要是介绍[BZOJ 3811]玛里苟斯：线性基（详细证明），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

(点击这里查看原题

极其复杂的题目……看了一早上题解才看懂
分类讨论
k=1时，考虑每一位对答案的影响，若至少存在一个数第j位为1，那么异或和中第j位为1的概率为0.5，否则为零。因为取到奇数个第j位为1的数的概率和取到偶数个的概率相等。
k=2时，把异或和转化为2进制，那么每个异或和的平方为${\sum }_i{\sum }_j{b}_i{b}_j\ast 2^{i+j}$，那么考虑第i位和第j位的积的期望值。如果所有的a[]中，第i位和第j位均相等且非全零，那么参考k=1的情况，期望为1/2；否则，i为1的概率为1/2，j位1的概率为1/2，i*j为1的概率为1/4。
k>=3时，因为答案不超过2^{63，因此a[i]不会超过2}21，线性基不会超过21个，于是求出线性基后暴力枚举。
需要注意的是，答案不会溢出，但中间过程可能会，因此需要将y变成$\lfloor \frac{y}{2^m}\rfloor \ast 2^m+ymod{2}^m$的形式。
这里需要证明一下$\lfloor \frac{x^k}{2^m}\rfloor \ast x+\lfloor \frac{(x^{k}mod{2}^m)\ast x}{2^m}\rfloor =\lfloor \frac{x^{k+1}}{2^m}\rfloor$
设$x^k=a\ast 2^m+b(b<2^m)$
于是等式左边$=ax+\lfloor \frac{bx}{2^m}\rfloor$
等式右边$=\lfloor \frac{x^k\ast x}{2^m}\rfloor =\lfloor \frac{ax\ast 2^m+bx}{2^m}\rfloor =ax+\lfloor \frac{bx}{2^m}\rfloor$
等式左右相等，即证。

/*
User:Small
Language:C++
Problem No.:3811
*/
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define inf 999999999
using namespace std;
const int M=1e5+5;
int n,q;
ull a[M],b[65];
void solve1(){ull res=0;for(int i=1;i<=n;i++) res|=a[i];printf("%llu",res>>1);if(res&1) printf(".5");printf("\n");
}
void solve2(){ull ans=0,res=0;for(int i=32;i>=0;i--){for(int j=32;j>=0;j--){bool flag=0;for(int k=1;k<=n;k++)if(a[k]>>i&1){flag=1;break;}if(!flag) continue;flag=0;for(int k=1;k<=n;k++)if(a[k]>>j&1){flag=1;break;}if(!flag) continue;flag=0;for(int k=1;k<=n;k++)if((a[k]>>i&1)!=(a[k]>>j&1)){flag=1;break;}if(i+j-1-flag<0) res++;//只有 (i,j)=(0,0)或(0,1)时有可能出现这种情况，//(i,j)=(0,0)时flag一定为0，因此对答案的影响是(1/2)*(2^0)=1/2；//(i,j)=(0,1)且flag=1时，对答案的影响是(1/4)*(2^1)=1/2。//因此出现这种情况时答案加1/2 else ans+=1LL<<(i+j-1-flag);//flag=0，则为1/2，flag=1，则为1/4 }}ans+=res>>1;printf("%llu",ans);if(res&1) printf(".5");printf("\n");
}
void solve3(){vector<ull> g;int cnt=0;for(int i=1;i<=n;i++){for(int j=22;j>=0;j--){if(a[i]>>j&1){if(b[j]) a[i]^=b[j];else{b[j]=a[i];cnt++;g.push_back(a[i]);break;}}}}ull ans=0,res=0;for(int i=0;i<(1<<cnt);i++){ull val=0;for(int j=0;j<cnt;j++) if(i>>j&1) val^=g[j];ull a=0,b=1;for(int j=0;j<q;j++){a*=val,b*=val;a+=b>>cnt,b&=(1<<cnt)-1;//对b取模 }ans+=a,res+=b;ans+=res>>cnt,res&=(1<<cnt)-1;}printf("%llu",ans);if(res) printf(".5");printf("\n");
}
int main(){freopen("data.in","r",stdin);//scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%llu",&a[i]);if(q==1) solve1();else if(q==2) solve2();else solve3();return 0;
}

这篇关于[BZOJ 3811]玛里苟斯：线性基（详细证明）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---