题解 P3898 【[湖南集训]大新闻】

· · 题解

传送门

题意简述

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

解题思路

我们先考虑暴力的解法。

35pts

当$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位，有下列情况：

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

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