清华集训2014 玛里苟斯
upd：结论证明已加入
题解
k=1
对于每一位分开考虑。
如果这一位可能被异或出来，那么就有\(1/2\)的概率出现。
直接计算即可。
k=2
\[ ans=\sum_{i=0}^{31}\sum_{j=0}^{31}d_{i,j}2^{i+j} \]
其中\(d_{i,j}\)表示异或和中\(2^i,2^j\)这两位同时出现的概率。
\(d_{i,j}\)怎么计算呢？
如果任意一位不可能出现，为0。
如果不可能独立出现，为\(\frac{1}{2}\)。
否则为\(\frac{1}{4}\)。
k>2
由于k比较大，答案\(<2^{63}\)，所以每个数\(<2^{22}\)。
那么线性基不超过22个数。
维护线性基直接暴力就可以了。
一个奇怪的结论
对于任意k，答案的小数部分要么是0要么是0.5。
当k=1和k=2时可以根据算法过程证明。
upd：结论的证明：参考sengxian博客下的评论（Orz Bill Yang）
考虑一个显然的思路：枚举k个位\(a_1..a_k\)(每一位互相独立且有顺序可以相同)，然后计算这k位同时为1的概率\(\times 2^{\sum a_i}\)求和。（也就是k=2的方法）
如果其中任意一位不可能为1，则概率为0（显然不影响）
如果概率为\(\frac{1}{2^i}\)，则\(a_1..a_k\)中至少有i个不同的项，那么至少有一项\(\ge i-1\)，那么它对\(2^{\sum_{a_i}}\)就至少有\(2^{i-1}\)的贡献。
然后\(2^{i-1}\times\frac{1}{2^i}=\frac{1}{2}\)就抵消掉了。
所以答案就只会有\(\frac{1}{2}\)而不是\(\frac{1}{4}\)等。
（如果是伪证欢迎disqus评论打脸）
代码
/*
Author: CNYALI_LK
LANG: C++
PROG: malygos.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef unsigned long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
ll linear[66],basis[66],k,s[66],a[233333];
void insert(ll x){
for(ll i=60;~i;--i){
if(x&(1LL<<i))
if(linear[i]) x^=linear[i];
else{
linear[i]=x;
for(ll j=i-1;~j;--j)if(linear[i]&(1LL<<j))linear[i]^=linear[j];
for(ll j=60;j>i;--j)if(linear[j]&(1LL<<i))linear[j]^=linear[i];
k=0;
for(ll j=0;j<60;++j)if(linear[j]){basis[k]=linear[j];++k;}
break;
}
}
}
int main(){
#ifdef cnyali_lk
freopen("malygos.in","r",stdin);
freopen("malygos.out","w",stdout);
#endif
ll n,m;
n=read();
m=read();
for(ll i=1;i<=n;++i)a[i]=read();
if(m==1){
ll ans=0;
for(ll i=1;i<=n;++i)ans|=a[i];
if(ans&1)printf("%llu.5\n",ans>>1);
else printf("%llu\n",ans>>1);
}
else if(m==2){
ll res=0,ans=0;
for(ll i=0;i<32;++i)for(ll j=0;j<32;++j){
ll as,b,c;
as=b=c=0;
for(ll k=1;k<=n;++k){
if(!!(a[k]&(1LL<<i))!=!!(a[k]&(1LL<<j)))as=1;
if(a[k]&(1LL<<i))b=1;
if(a[k]&(1LL<<j))c=1;
}
if(b&&c){
if((int)(i+j)-1-(int)as<0)++res;
else{
ans+=1ULL<<(i+j-1-as);
}
}
}
ans=ans+(res>>1);
res&=1;
printf("%llu%s",ans,res?".5\n":"\n");
}
else{
for(ll i=1;i<=n;++i)insert(a[i]);
ll ans=0,res=0;
for(ll i=0;i<(1<<k);++i){
ll as=0,xres=1,sum=0;
for(ll j=0;j<k;++j)if(i&(1<<j))as^=basis[j];
for(ll l=1;l<=m;++l){
sum=sum*as;
xres=xres*as;
sum+=xres>>k;
xres&=(1<<k)-1;
}
res+=xres;
ans+=sum+(res>>k);
res&=(1<<k)-1;
}
printf("%llu%s",ans,res?".5\n":"\n");
}
return 0;
}