题面

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)

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;
}

标签: 分类讨论, 线性基, 期望

添加新评论