CF1866M Mighty Rock Tower

CF题面 luogu题面

期望题。

题目大意：一个人在搭积木，每次堆叠可能成功或失败，失败可能导致其下面连续的若干块掉落。给定搭每一块时失败的概率，求堆叠完成的期望次数。
具体的，假设当前正在堆叠第 i 块，设掉落概率为 p，则有 p 概率第 i 块失败，有 $p^2$ 概率第 i 块和第 i-1 块均掉落，有 $p^3$ 概率第 i, i-1, i-2 块均掉落，以此类推。

设 $f_i$ 表示堆叠 $i$ 块的期望次数不好转移，注意到堆叠连续性，考虑设 $f_i$ 表示由第 $i-1$ 块到堆好第 $i$ 块的期望次数。

列出状态转移方程：
$f_i=(1-p_i)\times 1+p_i((1-p_i)(f_i+1)+p_i((1-p_i)(f_i+f_{i-1}+1)+\cdots +p_i(f_i+f_{i-1}+\cdots +f_1+1)\dots ))$

变形得 $f_i(1-p_i)=1+p_i^2\times f_{i-1}-p_i^3\times f_{i-1}+p_i^3\times (f_{i-1}+f_{i-2})+\cdots +p_i^{i-1}(f_{i-1}+f_{i-2}+\cdots +f_2)+p_i^i(f_{i-1}+f_{i-2}+\cdots +f_2+f_1)$

化简 得 $f_i=\frac{1+{\sum }_{j=2}^i{p}_i^j\times f_{i-j+1}}{1-p_i}$

这时复杂度是 $O(N^2)$，考虑如何优化。
我们当然想将 $f_{i-j+1}$ 转成前缀和，麻烦在于 $p_i^j$，这时我的思路卡死。
考虑如何处理 $p$，发现 $p\in [0,100)$，于是可以考虑对于所有 $p$ 都做前缀和维护。

这里再细讲下如何前缀和维护。对于 ${\sum }_{j=2}^i{P}^j\times f_{i-j+1}$，观察 $i+1$ 的和，即 ${\sum }_{j=2}^{i+1}{P}^j\times f_{i-j+2}$，发现就是 前者 $\times P+P^2\times f_i$。如果把求和的式子改写成 ${\sum }_{j=1}^{i-1}{P}_i^{i-j+1}\times f_j$ 会好看些，这里不写了。当然，学会观察式子并将之改得更加容易理解也是一种技能。

然后这题就做完了，时间复杂度 $O(100N\log M)$。
这题时限 2s，注意优化常数。
优化后的复杂度是 $O(100N)$，可以通过此题。

---

这题的关键点在于发现 $p\in [0,100)$ ，可以将前缀和关于 $p$ 全部维护出来。

$Code$