P8967 题解（2023 激励计划评分 10）

mc123456 · 2023-11-12 23:39:26 · 题解

神仙期望（确信）。

分析

对于期望题，通常考虑 dp。这里设 f_i 表示从第 i 个点走到终点的期望步数。那么 f_i 就是两部分的和，一部分是直接走到终点的期望，一部分是散入天际后再走到重点的期望。

直接走到终点

对于第一部分，令 q_i 表示从第 i 个点直接走到终点的概率，P 表示 \sum\limits_{i = 1}^{k}{p_i}。那么我们可以发现：

• 若 \exists j, a_{i, j} > d_j，那么第 i 个点永远无法直接走到终点，即 q_i = 0。

• 否则 \forall j, a_{i, j} \leq d，那么第 i 个点想直接走到终点需要走 s_i = \sum\limits_{j = 1}^{n}{d_j - a_{i, j}} 步。每步不散入天际的概率是 1 - P，总的不散入天际的概率是 (1 - P)^{s_i}。走 s_i 步一共有 n^{s_i} 种走法，其中只有 \dfrac{s_i!}{\prod\limits_{j = 1}^{n}{(d_j - a_{i, j})!}} 种走法是可以到达终点的。故此时有：

  q_i = (1 - P)^{s_i} \cdot \dfrac{1}{n^{s_i}} \cdot \dfrac{s_i!}{\prod\limits_{j = 1}^{n}{(d_j - a_{i, j})!}}

那么这一部分的期望步数就是 q_i \cdot s_i。

散入天际

这一部分较为复杂。如果直接考虑用 f_j 来表示 f_i，则 f 成了一个 k 元线性方程组，那么使用高斯消元将有 O(k^3) 的复杂度，显然无法通过此题。

注意到无论从哪里散入天际，这之后走到终点的期望都是一定的，不妨设这个期望为 r。那么我们只需考虑从第 i 个点走，期望散入天际的步数 g_i，并将这两个数求和即可。

如此可以轻易得到 r 的表达式：

对于不考虑走到终点停下，期望散入天际的步数，可以得出为 {g_1}_i = \sum\limits_{j = 1}^{\infty}{j \cdot (1 - P)^{j - 1} \cdot P} = \dfrac{1}{P}。若走到了终点，那么这一部分期望就为走到终点的期望加上走到终点后的期望，为 {g_2}_i = q_i \cdot (s_i + \dfrac{1}{P})。那么总的期望散入天际的步数就是这两个的差，即：

推式子

综合上述两部分，我们就得到了 f_i 的表达式，即：

再根据 r = \sum\limits_{i = 1}^{k}{\dfrac{p_i \cdot f_i}{P}}，将 f_i 代入，得：

移向，整理，通分，得：

最后，将 r 代回，得到：