题解 CF1264C 【Beautiful Mirrors with queries】

• CF1264C 【Beautiful Mirrors with queries】

一道期望入门好题，有着非常巧妙的解法。

---

• Prelude

对于这个题面我们一眼望去会想到线性递推一个期望dp式子求解。

但是发现无法实现。

原因很明显，对于断点的修改和维护，我们并不能每次都重新 \(O(n)\) 做一遍

我又想到用数据结构维护答案，但是其实大材小用了。

其实我们只需要推出一个区间的通项式来 \(O(1)\) 求解即可。

这种思路其实经常存在于一些线段树的数据结构题中，推出可行的懒惰标记的 \(O(1)\) 下传公式。

至少我是在 \(\texttt{P6327}\) 和 \(\texttt{P2122}\) 中深有这种体会。

---

• Solution

推dp时，我们考虑题面中 \(\text{从编号小于等于当前镜子的且最近的检查点开始提问}\) 中不难想到为了防止后效性，我们

应该定义 \(f_i\) 为从 \(i\) 点开始询问一直到 \(n\) 点的期望值。

起初每次伤心后会从第一个点开始。则有

\[f_i=p_i\times f_{i+1}+(100\%-p_i)\times f_1 \]

移项消元得到

\[f_1=\frac{1}{p_n}+\frac{1}{p_n\times p_{n-1}}+\dots+\frac{1}{p_n\times p_{n-1}\times \dots\times p_{1}} \]

毕竟 \(f_1\) 就是 \(f(1\rightarrow n)\) ，那么根据 期望 的线性性质我们可以引入区间 \([l,r]\) ( \(l,r\) 都是复活点), 可以得到

\[f_l-f_r=f(l\rightarrow r)=\frac{1}{p_r}+\frac{1}{p_r\times p_{r-1}}+\dots+\frac{1}{p_r\times\dots\times p_l} \]

\[=\frac{\prod_{i\in [l,r-1]}p_i+\prod_{i\in [l,r-2]}p_i+\dots+p_l+1}{\prod_{i=1}^rp_i/\prod_{i=1}^{l-1}p_i} \]

那么现在我们又只需要维护：

• \(\displaystyle m_x=\prod_{i=1}^{x}p_i\) (分母)；
• \(\displaystyle s_x=\sum_{i=1}^xm_i\) (分子)；
• 和 \(\displaystyle ans=\sum_{l,r\in \texttt{check-points}} f(l\rightarrow r)\)；

每次修改的 \(\texttt{check-points}\) 可以用 set 在 \(O(\log n)\) 时间维护。

---

• Code

题面有要求求逆，而逆元可以直接用快速幂求解。

#include
#include
#include
#include
#include
#include
#include