自动搬运

查看原文

来自洛谷，原作者为

	一只绝帆 就让我在风儿中独舞，唱着只有云儿能听懂的哀歌。

搬运于2025-08-24 22:50:14，当前版本为作者最后更新于2023-09-10 21:12:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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

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

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

$$\begin{aligned} & \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)$。

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

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

$$\begin{aligned} \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$ 吧！

$$\begin{aligned}S_k&=\frac{(1-p)^{(k+1)x}(k+1)-\sum\limits_{i=1}^k(1-p)^{ix}-1}{(1-p)^x-1}\\&=\frac{(1-p)^{(k+1)x}(k+1)-\frac{(1-p)^{(k+1)x}-(1-p)^x}{(1-p)^x-1}-1}{(1-p)^x-1} \end{aligned}$$

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

• $(1-p)^{(k+1)x}(k+1)$：由于左方是指数式子，增长率一定比右边的线性式子快，所以 $(1-p)^{(k+1)x}(k+1)\to 0$。

• $(1-p)^{(k+1)x}\to 0$，这个很显然。

所以：

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