[BZOJ 3652] 大新闻

题意

随机从 \([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 <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;

}