- 清华集训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)，直接暴力枚举计算期望。
- 这题有一个结论是答案两倍一定是整数，也就是答案的小数最多有一位；
- (kleq3)比较好证，但是(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;
}