2025-2026:teams:the_server_is_busy_please_try_again_later:20250729
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2025-2026:teams:the_server_is_busy_please_try_again_later:20250729 [2025/08/03 00:31] ender_hz |
2025-2026:teams:the_server_is_busy_please_try_again_later:20250729 [2025/08/03 14:27] (当前版本) istina |
||
|---|---|---|---|
| 行 56: | 行 56: | ||
| 时间复杂度 $\mathcal O(t^2n\log b)$ ，可以通过本题。 | 时间复杂度 $\mathcal O(t^2n\log b)$ ，可以通过本题。 | ||
| + | ===== L（_istina_ 补）==== | ||
| + | |||
| + | 将总期望尝试次数拆成 $b > 0$ 和 $b = 0$ 两部分（可能在第一部分中已经达成目标，那么第二部分就没有被经过） | ||
| + | |||
| + | 先考虑 $b > 0$ 的情形。考虑二维状态 $(i, j)$ ，表示当前 $a = i$，$b = z - j$。初始状态为 $(0,0)$ ，目标状态为 $(n,?)$ 。状态转移为：有 $p$ 的概率 $(i,j)\to (i+1,j)$ ，$(1 - p)$ 的概率 $(i,j) \to (i, j + 1)$。由于不会走回头路，第一部分的期望步数就是所有状态的概率之和。 | ||
| + | |||
| + | 假设 $P_{i,j}$ 表示经过某状态的概率，可得方程： | ||
| + | $$ | ||
| + | P_{i,j}=\begin{cases} | ||
| + | 1 &\text {if } i, j = 0 | ||
| + | \\ | ||
| + | p P_{i - 1, j} &\text{if } j = 0 | ||
| + | \\ | ||
| + | (1-p)P_{i, j - 1} & \text{if } i = 0 | ||
| + | \\ | ||
| + | pP_{i - 1,j}+(1 - p)P_{i,j - 1} & \text{if } i, j\neq 0 | ||
| + | \end{cases} | ||
| + | $$ | ||
| + | 设 $S_j = \sum_{i = 0}^{n - 1}P_{i, j}$，由于 $P_{i, j} = pP_{i - 1, j} + (1 - p)P_{i, j - 1}$ ， 累加可得： | ||
| + | $$ | ||
| + | \sum_{i = 0} ^ {n - 1} P_{i, j} = p\sum_{i = 0} ^{n - 1}P_{i - 1, j} + (1 - p) \sum_{i = 0}^{n - 1} P_{i, j - 1} | ||
| + | $$ | ||
| + | 整理之后可得： | ||
| + | $$ | ||
| + | S_j = p(S_j - P_{n - 1, j} + P_{-1, j})+(1 - p)S_{j - 1} | ||
| + | \\ | ||
| + | S_j = S_{j - 1}-\frac p {1 - p} P_{n - 1, j} | ||
| + | \\ | ||
| + | S_0 = \frac{1 - p^n}{1 - p} | ||
| + | $$ | ||
| + | 再结合 $P_{n - 1, j}$ 的递推式： | ||
| + | $$ | ||
| + | P_{n - 1, j} = C_{n - 1 + j}^{j}p^{n - 1}(1 - p)^{j} = \frac{(n - 1 + j)(1 - p)}{j} P_{n - 1, j - 1} | ||
| + | $$ | ||
| + | 就可以通过递推得到 $S_j$ ，而对于每个 $z$ ，这一部分的答案就是 $\sum_{j = 0}^{z}S_j$。 | ||
| + | |||
| + | 再考虑 $b = 0$ 的情形。这一部分的期望尝试次数是好计算的。 | ||
| + | |||
| + | 设从 $a$ 从 $0$ 到 $i$ 期望尝试次数为 $D_i$ ，从 $i - 1$ 到 $i$ 的期望尝试次数为 $d_i$ ，则可以得到以下式子： | ||
| + | $$ | ||
| + | \begin{align} | ||
| + | \begin{cases} | ||
| + | d_i = p + (1 - p) (D_i+1) | ||
| + | \\ | ||
| + | d_i = D_i - D_{i - 1} | ||
| + | \end{cases} | ||
| + | \end{align} | ||
| + | $$ | ||
| + | 可以解得： | ||
| + | $$ | ||
| + | pD_i = D_{i - 1} + 1 | ||
| + | \\ | ||
| + | p(D_i + \frac{1}{1-p}) = D_{i - 1} +\frac{1}{1 - p} | ||
| + | \\ | ||
| + | D_i = \frac{1 - p^i}{(1 - p)p^i} | ||
| + | $$ | ||
| + | 而进入第二部分的概率就是是简单的 $S_z(1-p)$ ，将概率和期望尝试次数相乘即为第二部分的答案。 | ||
| + | |||
| + | 总体上时间复杂度为 $\mathcal O (m\log m)$ ，可通过预处理逆元优化为线性。 | ||
| ===== 总结 ===== | ===== 总结 ===== | ||
2025-2026/teams/the_server_is_busy_please_try_again_later/20250729.txt · 最后更改: 2025/08/03 14:27 由 istina
