P9627 Sol

· · 题解

upd on 2023.9.12:成小丑了

高中数学选修三告诉我们有一个东西叫几何分布。

简单来说就是你做某件事，每次 p 的概率成功，不成功就从头再来，则期望进行次数 \frac 1 p，这个很好理解吧，如果每次花费 x 的代价，则期望代价 \frac x p。

于是我可爱的又臭又长的式子就只有最后证明凸函数是有用的了。

原题解：

我不知道为什么这个题大家过的这么猛。

我只知道我写了两黑板的式子，中间还推错了两次。

公式量可能较大。

首先简化一下题意，假装造一个烟花只需要 1 的代价，也就是 m\gets \frac m n，最后再 ans\gets ans\times n。

考虑一个最优策略一定是造 x 个烟花检查一次，造 x 个烟花检查一次，这个 x 一定是定值（因为如果检查失败了那么可以规约到最开始的时刻）。

那我们考虑写出一个关于 x 的式子然后求最值。

第一组就成功的概率是 1-(1-p)^x，时间是 x+m；第二次成功概率是 (1-p)^x(1-(1-p)^x)，时间是 2(x+m)……

（注意不是 2x+m，因为你做完前 x 个并不能实时知道自己成功了没有。）

所以我们可以写出答案：

\sum_{i=0}^{\infty}(1-p)^{ix}\left(1-(1-p)^x\right)(i+1)(x+m)

无穷级数肯定求不了一点，那我们考虑化简这个可爱的东西。

首先是把无用项提到前面。

& \sum_{i=0}^{\infty}(1-p)^{ix}\left(1-(1-p)^x\right)(i+1)(x+m) \\ =\ & \left(1-(1-p)^x\right)(x+m)\sum_{i=0}^{\infty}(1-p)^{ix}(i+1)\\ \end{aligned}

然后我们考虑如何求这个东西：\sum_{i=0}^{\infty}(1-p)^{ix}(i+1)。

这不是普通的等比数列求和，也不是等差数列求和，而是等比等差数列各项分别相乘再求和。

我们可以用类似于推等比数列求和公式的方法来推。

\texttt{设}\ S_{k}&=\sum_{i=0}^{k}(1-p)^{ix}(i+1)\\ \texttt{则}\ (1-p)^xS_k&=\sum_{i=0}^k(1-p)^{(i+1)x}(i+1) \\ &=\sum_{i+1=1}^{k+1}(1-p)^{(i+1)x}(i+1) \\&=\sum_{i=1}^{k+1}(1-p)^{ix}i\\\texttt{则} \ (1-p)^xS_k-S_k&=(1-p)^{(k+1)x}(k+1)-\sum_{i=1}^k(1-p)^{ix}-1\\\texttt{则}\ S_k&=\frac{(1-p)^{(k+1)x}(k+1)-\sum\limits_{i=1}^k(1-p)^{ix}-1}{(1-p)^x-1}\end{aligned}

发现好像还有一个可爱的 \sum，但是此时已经是等比数列求和了，简单搞一搞：

\begin{aligned}\texttt{设}\ T_{k}&=\sum_{i=1}^k(1-p)^{ix}\\\texttt{则}\ (1-p)^xT_k&=\sum_{i=1}^k(1-p)^{(i+1)x}\\&=\sum_{i+1=2}^{k+1}(1-p)^{(i+1)x}\\&=\sum_{i=2}^{k+1}(1-p)^{ix}\\\texttt{则}\ (1-p)^xT_k-T_k&=(1-p)^{(k+1)x}-(1-p)^x\\\texttt{则}\ T_k&=\frac{(1-p)^{(k+1)x}-(1-p)^x}{(1-p)^x-1}\end{aligned}

好！

那我们接着化简 S_k 吧！

\end{aligned}

然后我们令 k\to \infty，分别讨论每个含 k 的式子。

所以：

\begin{aligned}S_{\infty}&=\frac{-\frac{-(1-p)^x}{(1-p)^x-1}-1}{(1-p)^x-1}\\&=\frac{1+\frac{(1-p)^x}{1-(1-p)^x}}{1-(1-p)^x}\end{aligned}

那么就可以求出答案了：

\begin{aligned}ans&=\left(1-(1-p)^x\right)(x+m)S_{\infty}\\&=\left(1-(1-p)^x\right)(x+m)\frac{1+\frac{(1-p)^x}{1-(1-p)^x}}{1-(1-p)^x}\\&=(x+m)\left(1+\frac{(1-p)^x}{1-(1-p)^x}\right)\\&=(x+m)\left(\frac{1}{1-(1-p)^x}\right)\\&=\frac{x+m}{1-(1-p)^x}\end{aligned}

但是由于我们 x 是设好的常量，我们还得对 x 求 \min\limits_x\frac{x+m}{1-(1-p)^x}。

画出函数图像下面我们证一下这个东西是凸的。

\begin{aligned} \texttt{设} \ f(x)&=\frac{x+m}{1-(1-p)^x}\\\texttt{则}\ f'(x)&=\frac{\ln\left(1-p\right)\left(1-p\right)^x\left(x+m\right)}{\left(1-\left(1-p\right)^x\right)^2}+\dfrac{1}{1-\left(1-p\right)^x}\end{aligned}

后面那一项显然随 x 增大而减小，前面那一项的 (1-p)^x(x+m) 乘起来是单减的，分母是单增的，所以总体就是单减的。

所以该函数切线斜率随 x 增大而减小，是凸函数。

（不会求导，现去求导软件上扒拉的/kk。）

既然是凸的，直接三分即可。

Code：

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##end(b);i<=i##end;i++)
#define gc getchar
using namespace std;typedef long double db;
int read() {
    int s=0;char c=gc(),w=0;
    while(c<'0'||c>'9') w|=c=='-',c=gc();
    while(c>='0'&&c<='9') s=s*10+(c^48),c=gc();
    return w?-s:s;
} const db eps=1e-13;
db n,m,p,q;
db check(db x) {return (x+m)/(1-pow(1-p,x));}
int main() {
    F(T,1,read()) {
        n=read();m=(db)read()/n;p=(db)read()/10000;q=1-p;
        int L=1,R=1e9,mid;
        while(L<=R) {
            mid=L+R>>1;
            if(L+10>=R) break;
            if(check(mid)<check(mid+1)) R=mid+1;
            else L=mid;
        } db ans=1e20;
        F(i,L,R) ans=min(ans,check(i));
        printf("%.10Lf\n",ans*n);
    }
    return 0;
}