自动搬运

查看原文

来自洛谷，原作者为

	wlj_55 **

搬运于2025-08-24 21:53:51，当前版本为作者最后更新于2019-10-16 12:05:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传送门

题意简述

有两个数$x,y$，其中$x$是随机生成的$[0,n)$间一个正整数，$y$有$p$的概率为$[0,n)$间一个数，使得$x\space xor\space y$最大，有$(1-p)$的概率生成方式同$x$，求$x\space xor \space y$的期望值。

解题思路

我们先考虑暴力的解法。

35pts

$n\le100$，随便怎么暴力都可以过。

当$p=0$时，即求

$$\frac{\sum_{i=1}^n\sum_{j=1}^n i\space xor\space j}{n^2} $$

直接两重循环求解即可，时间复杂度$O(n^2)$，记得开$double$

当$p=1$时，我们只需对上述情况的第二层循环做出微调，将求和改为求最大值，再讲每一个$i$所对应的最大值分别相加即可。

代码略。

50pts

我们可以观察到后面$15pts$的数据是$2^k$的形式，那么它们间一定有着一些特殊规律。

经打表检验得：

当$p=0$时，答案为$\frac{n-1}{2}$

当$p=1$时，答案为$n-1$

下面给出证明：

首先，在$p=1$时，对于每个数$x$，总有一个数$y∈[0,n)$使得$x\space xor \space y=n-1$，所以期望为$\frac{n(n-1)}{n}=n-1$

在$p=0$时，我们首先有一个结论：

$$x\space xor\space i+x\space xor\space (2^k-i-1)=2^k-1\qquad i∈[0,2^k) $$

证明也很简单，手玩一下就好了。

所以我们对$[0,n)$间数两两配对，求得期望为$\frac{n\times \frac{n\times(n-1)}{2}}{n^2}=\frac{n-1}{2}$

100pts

由于这里有$0\le p\le1$的情况，所以我们要先解决这种情况。

设$P$为总的期望值，$P_1$为$p$取$0$时的期望，$P_2$为$p$取$1$时的期望，

由期望的一些基本知识可以很容易的推出

$$P=(1-p)\times P_1+p\times P_2$$

那么下面就是如何计算$P_1,P_2$的问题了。

先讨论$p=0$时的情况，

我们设对于两个数异或起来的值，第$i$位为$1$为事件$A$，第$j$位为$1$为事件$B$，由位运算的性质知$A,B$相互独立，故我们可以分开计算。

我们再设从$[0,n)$中选出一个数，其二进制第$i$位为$1$的概率为$p_i$，那么刚才的答案就是

$$\sum_{i=0}^{\log n}2\times p_i\times (1-p_i)\times2^i $$

考虑对于区间$[0,2^{k})$，一定有区间$[0,2^{k-1})$的所有数的第$k$位均为$0$，区间$[2_{k-1},2^k)$的所有数第$k$位均为$1$。

然后我们考虑区间$[0,n)$，那么必定有区间$[S\times 2^{k},S\times2^k+2^{k-1})$中的数第$k$位为0，区间$[S\times2^k+2^{k-1},(S+1)\times2^{k+1})$中数的第$k$位为0，所以第$k$位为1的数的个数是：

$$\lfloor\frac{n}{2^{k+1}}\rfloor\times 2^k+max(n\space mod\space2^{k+1}-2^k,0) $$

故概率$p_i$为

$$\frac{\lfloor\frac{n}{2^{k+1}}\rfloor\times 2^k+max(n\space mod\space2^{k+1}-2^k,0)}{n} $$

时间复杂度$O(\log n)$

我们再来考虑$p=1$时的情况（比较毒瘤）

我们设$f(x)$为$[0,n)$内使$x\space xor\space f(x)$最大的$f(x)$的值

如果没有范围的限制的话，$f(x)$应为$x$按位取反后的值，现在多了一个$n$的限制，那我们可以考虑用一种贪心的手法保留高位的$1$，如果某一位取$1$会使$f(x)\ge n$，那么这一位就只能取$0$。

我们考虑最高的$i-1$位$(i-1\ge0)$和$n-1$的前$(i-1)$位相同的所有的$x$对答案的贡献，我们考虑$n-1$与$x$的第$i$位，有下列情况：

$1.n-1$的第$i$位为$0$，由于$x\le n-1,f(x)\le n-1$，所以$x$的第$i$位和$f(x)$的第$i$位必须为$0$。

$2.n-1$的第$i$位为$1$，那么$x$第$i$位的取值又可以分两种情况：

①$:x$的第$i$位为$1$，那么$f(x)$的第$i$位为$0$，且以后的位数一定可以取$x$取反后的值。

②$:x$的第$i$位为$0$，那么$f(x)$的第$i$位为$1$，但还有后面的限制。

每次处理时$n-1$的规模将减半，故时间复杂度为$O(\log n)$

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
double solve1(ll n){
	double ret=0;
	ll Pow=0,tmp=n-1;
	while(tmp!=0){
		Pow++;
		tmp>>=1;
	}
	for(int i=Pow;i>0;i--){
		ll nw=(n>>i)*(1LL<<i-1)+min(n-(n>>i<<i),1LL<<i-1);
		double p=double(n-nw)/n;
		ret+=(1.0-p)*(1LL<<(i-1))*p;
	}
	return ret*2.0;
}
double solve2(ll n){
	if(n==1)  return 0.0;
	double ret=0.0;
	ll v=1LL,delta,num,tmp=n-1;
	n--;
	while(v<=tmp){
		v<<=1;
	}
	delta=v-1LL;
	v>>=1;
	ret+=(double)delta*(n-v+1);
	ret+=(double)v*v;
	num=v,delta>>=1;
	while(v!=1){
		v>>=1,delta>>=1;
		if(n&v){
			ret+=(double)num*v;
			ret+=(double)(num>>1)*delta;
			num>>=1;
		}
		else
		  ret+=(double)(num>>1)*v;
	}
	return ret/(double)(n+1);
}
int main(){
	ll n;
	double p;
	scanf("%lld%lf",&n,&p);
	double p1=solve1(n),p2=solve2(n),ans=(1.0-p)*p1+p*p2;
	printf("%.6lf\n",ans);
}

如果大家有不懂的可以问我，我会尽我所能解答。