洛谷 P3898 [湖南集训]大新闻

挺妙的数位 dp + 概率 / 期望题

---

题意

给定数 $n$ 。
$x$ 为一个在 $[0,n)$ 范围内随机分布的数。
对数 $x$ 的操作有两种情况：

• 若数 $x$ 被加密过，则在 $[0,n)$ 范围内随机选择一个数 $y$ ，令 $x \rightarrow x \bigoplus y$ 。
• 若数 $x$ 没有被加密过，则选择一个 $[0,n)$ 范围内的数 $y$ 使得 $x \bigoplus y$ 最大，并令 $x \rightarrow x \bigoplus y$ 。

其中 $x$ 有 $p$ 的概率没有被加密过，求操作后 $x$ 的期望值。
其中 $1 \leq n \leq 10^{18}, 0 \leq p \leq 1$ 。

思路

首先未加密和加密两种情况的期望可以分开来算再合并。
假设未加密和加密情况下 $x$ 的期望分别为 $ans_0, ans_1$ ，那么答案即为 $ans = p \cdot ans_0 + (1 - p) \cdot ans_1$ 。

对于加密的情况：
加密的情况相比比较简单，最后结果的期望值等价于所有事件的权值之和除以事件总数，即有：

$$ans_1 = \frac{\sum\limits_{x=0}^{n-1}\sum\limits_{y=0}^{n-1} (x \bigoplus y)}{n^2}$$

按照二进制位分开算每一位的贡献即可。

对于未加密的情况：
类似加密的情况可以写出式子：

$$ans_0 = \frac{\sum\limits_{x=1}^{n-1} \max\limits_{y=0}^{n-1} (x \bigoplus y)}{n}$$

考虑如果是单个数 $x$ ，确认 $y$ 只需要按二进制从高位到低位枚举一遍，如果 $x$ 对应位为 $0$ 并且 $y$ 加上这一位的 $1$ 后不会超过 $n-1$ ，就贪心地加上，最后结果即是。
但 $n$ 的范围非常大 $\rightarrow [1,10^{18}]$ ，考虑能不能把特征相同的 $x$ 放在一起计算，考虑到 $x, y$ 的限制条件为 $x, y \in [0,n)$ ，若用类似的按位计算的方法，对于一些 $x$ 和 $y$ ，我们只需要知道在考虑到某一位时这一位的取值范围，可以用一个类似数位 $dp$ 的方式记录在考虑到最高 $i$ 位， $x, y$ 的当前位置分别有/无最高位限制时的总贡献和总方案数，最后再求和。
具体为：
$f[i][j][k]$ 表示考虑了最高 $i$ 位， $x$ 与 $y$ 的当前位置有无最高位限制 $(0/1)$ 时的总贡献。
$g[i][j][k]$ 表示考虑了最高 $i$ 位， $x$ 与 $y$ 的当前位置有无最高位限制 $(0/1)$ 时的方案数。
转移时候枚举 $i, j, a$ 的值（ $a \in [0,1]$ 为 $x$ 这一位填入的数），并计算出对应应填入 $y$ 该位的值进行转移即可。

代码

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

constexpr int N=64;

ll n,bit[N];
double p;
double f[N][2][2],g[N][2][2];

double calc0(){
    if(n==1) return 0;
    ll tmp=n-1;
    double res=0;
    vector<int> vec;
    while(tmp){
        vec.push_back(tmp&1);
        tmp>>=1;
    }
    g[vec.size()][1][1]=1.0/n;
    for(int i=(int)vec.size()-1;i>=0;i--){
        for(int j=0;j<=1;j++)
            for(int k=0;k<=1;k++)
                for(int x=0;x<=(j?vec[i]:1);x++){
                    int y=x^1;
                    if(k&&y>vec[i]) y=0;
                    f[i][j&&x==vec[i]][k&&y==vec[i]]+=f[i+1][j][k]+1.0*bit[i]*g[i+1][j][k]*(x^y);
                    g[i][j&&x==vec[i]][k&&y==vec[i]]+=g[i+1][j][k];
                }
    }
    for(int j=0;j<=1;j++)
        for(int k=0;k<=1;k++) res+=f[0][j][k];
    return res;
}

double calc1(){
    ll tmp=n,m=0;
    while(tmp){
        tmp>>=1;
        m++;
    }
    double res=0;
    for(int i=m-1;i>=0;i--){
        double p=1.0*((n/bit[i+1])*bit[i]+max(n%bit[i+1]-bit[i],0ll))/n;
        res+=2*p*(1-p)*(1ll<<i);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    bit[0]=1;
    for(int i=1;i<N;i++) bit[i]=bit[i-1]*2;

    cin>>n>>p;
    cout<<fixed<<setprecision(8)<<p*calc0()+(1-p)*calc1();

    return true&&false;
}