BS-2247 选钻石 题解

题意

有一个长度为 \(n\) 的随机数列 \(\{p_i\}\)。每个 \(p_i\) 独立等概率在 \(1\sim m\) 中选取。

你选数的过程如下：

• 从 \(i=1\) 开始，每一步只能看到当前 \(p_i\) 。你需要决策是否选择 \(p_i\)：若选择，则直接结束；否则继续看 \(p_{i+1}\)。
• 不能回头选择 \(i\) 之前的数。

最大化选出的数的期望，求出这个最大期望。

\(1\le n\le 10^{9},2\le m\le 10^6\)。

Solution

由于每个数独立，\(i\) 之前的数对 \(i\) 处决策没有影响。不难得到一个 \(O(n)\) 的 DP：

设 \(f_i\) 为有 \(i\) 个数的最大期望，答案即为 \(f_n\)。

显然 \(f_1=(1+m)/2\)。对于一个位置 \(i\)：

• 若 \(p_i\le f_{i+1}\)（即 \(p_i\le \lfloor f_{i+1}\rfloor\)）那么不选 \(p_i\)
• 否则选 \(p_i\) 并退出

综上，设 \(t=\lfloor f_{i-1} \rfloor\)，转移方程为：

注意到 \(f\) 满足：

• \(f_i\) 单调递增
• \(f_i

因此 \(\lfloor f_{i} \rfloor\) 单调不降，当 \(\lfloor f_{i} \rfloor=m-1\) 后不再改变。

我们先暴力 DP 直到 \(f_{i}\ge m-1\)，设 \(a\) 为第一个满足此条件的 \(i\)。

此后转移方程变成：

这是一个一阶线性递推，不动点法得：

因此 \(f_n=(f_a-m)\left(\frac{m-1}{m}\right)^{n-a}+m\)，快速幂解决即可。

时间复杂度

我们可以证明，这个算法的时间复杂度是 \(O(m\log m)\)。

引理

首先考虑一个不优的策略：看到 \(m\) 就拿，否则一直跳过。这个策略在 \(k\) 个数时的期望为：

令

得

又因为策略不优，有

因此

令引理中 \(x=\frac{1}{m-1}\)，得

于是 DP 部分一定不会算超过 \(m\ln m\) 个，算法时间复杂度为 \(O(m\log m)\)。

Code

#include 
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define db double
using namespace std;
db ksm(db x,int y){
    db res=1;
    while(y){
        if(y&1) res*=x;
        x*=x,y>>=1;
    }
    return res;
}
signed main(){
    int n,m,i=1,t;
    cin>>m>>n;
    cout<