题意
随机从 $[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}$ 次贡献. 这部分同样要计算进去.
算完转成期望再加权求个和就没了.
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <bits/stdc++.h>
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<intEx> 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<<z.size());
for(auto x:z)
sum+=unit*x*wcnt*(1ll<<(z.size()-1));
}
else{
z.push_back(i);
}
}
sum+=unit*cur*(1ll<<z.size());
for(auto x:z)
sum+=unit*x*(1ll<<(z.size()-1));
sum/=n+1;
cur=0;
long double rd=0;
for(intEx i=mp;i!=0;i>>=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;
}
|
