2022-09-15-「Note」概率期望 DP 消除后效性的相关总结

或许这个 trick 很简单，但我确实是现在才知道。。。

这个方法其实是由局限性的，对于不定形的环是难以处理的。

用最近联考的一道简单题说明一下这个玩意。

$\mathbb{51Nod \ 5114}$

link

可以很轻松的拿出式子， $E(i) = E(i - 1) \times (1 - p_{i}) + E(i + 1) \times p_{i} + 1$ ，发现这个是有后效性的，可以想到用高斯消元，但是 $\Theta(n ^ 3)$ 一定过不了，则令 $E(i) = E(i - 1) \times k_i + c_i$ 表示这个式子，即是说把 $E(i)$ 表示成一个只和 $E(i - 1)$ 有关的式子。
则， $E(i + 1) = E(i) \times (1 - p_{i}) + c_{i + 1}$ ， 带回去，得到 $E(i) = E(i - 1) \times (1 - p_{i}) + E(i) \times k_{i + 1} + c_{i + 1} + 1$ ， 整理后变成 $E(i) = \large\frac{E(i - 1) \times (1 - p_{i}) + c_{i + 1} + 1}{1 - k_{i + 1}}$ 。
然后把 $(k_i, c_i)$ 当成一个二元组，显而易见的 $(k_n, c_n) = (0, 0)$ ，要求的是 $(k_1, c_1)$ 因为 $1$ 没有前驱，则 $E(1) = c_1$ ，则只需要迭代把 $c_1$ 求出来就可以了，由刚刚推出来的式子可知 $(k_i, c_i) = (\frac{1 - p_{i}}{k_{i + 1}}, \frac{c_{i + 1}}{k_{i + 1}})$

$\mathbb{HUD \ 4035}$

link

其实是差不多的，只是搬到了树上，把式子表示成只和 $fa_i$ 有关的一个多项式就可以了，常数项是所有子节点的贡献，因为课上讲过，就不写了。