大新闻

题意

随机从 \([0,n)\) 中选取一个整数 \(x\), 并从 \([0,n)\) 中再选取一个整数 \(y\). 有 \(p\) 的概率选取一个能令 \(x\operatorname{xor} y\) 最大的 \(y\), 否则会随机选取一个 \(y\). 求 \(x\operatorname{xor}y\) 的期望.

\(n\le 1\times 10^{18}\).

题解

一道情况不算多的特判题吧

首先随机决策的部分超级好算. 因为期望的线性性我们可以把每一位最后异或和为 \(1\) 的概率算出来求和作为这部分的答案. 方法就是计算出在所有 \([0,n)\) 的数中当前位为 \(0\) 的概率(这大概好算点) \(z\), 然后求 \(2z(1-z)\) 就是当前位为 \(1\) 的概率了.

以下默认将值域改为 \([0,n]\).

然后就是最优决策部分. 这部分显然会尽量让高位异或值为 \(1\). 那么我们要让 \(y\) 的高位尽量都与 \(x\) 相反. 注意到当出现第一个 \(n\) 中为 \(1\) 且 \(x\) 中为 \(1\) 的位之后, 后面的位就能够全部异或出 \(1\) 了(因为这时要想异或值最大需要让 \(y\) 的当前位置 \(0\), 那么后面的位无论如何取值都不会超过 \(n\) 的限制了), 我们称之为关键位. 于是我们枚举关键出现位置, 计算关键位为当前位置的所有 \(x\) 产生的贡献. 这时能够异或出的值即为 \(n\) 的高位加上低位全部置 \(1\) 的值.

但是这样还不够, 因为高位中还有三种可能情况: \(n\rightarrow1,x\rightarrow0;n\rightarrow0,x\rightarrow1;n\rightarrow0,x\rightarrow0\). 其中 \(n\rightarrow1,x\rightarrow0\) 和 \(n\rightarrow0,x\rightarrow0\) 的情况产生的贡献已经在上面计算过了. 而 \(n\rightarrow0,x\rightarrow1\) 的情况还需要计算. 若关键位前 \(n\) 中有 \(k\) 个 \(0\) 位, 那么每一位都会产生 \(2^{k-1}\) 次贡献. 这部分同样要计算进去.

算完转成期望再加权求个和就没了.

参考代码

#include 
    
     namespace rvalue{    typedef long long intEx;    int main(){        intEx n,mp=1;        double p;        scanf("%lld%lf",&n,&p);        --n;        while((mp<<1)<=n)            mp<<=1;        long double sum=0,unit=1;        std::vector
     
       z;        intEx cur=0;        for(intEx i=mp;i!=0;i>>=1){            if(i&n){                cur|=i;                intEx wcnt=std::min(i|(i-1),n)-i+1;                intEx xval=cur|(i-1);                sum+=unit*xval*wcnt*(1ll<
      
       >=1){            intEx cnt=cur*i+std::min((cur<<1)*i|(i-1),n)-(cur<<1)*i+1;            long double z=1.*cnt/(n+1);            rd+=z*(1-z)*2*i;            cur=(cur<<1)|(i&n?1:0);        }        printf("%.10Lf\n",p*sum+(1-p)*rd);        return 0;    }}int main(){    freopen("news.in","r",stdin);    freopen("news.out","w",stdout);    rvalue::main();    return 0;}