P5323 [BJOI2019] 光线 题解

__vector__ · 2023-10-18 21:12:27 · 个人记录

感觉是一道水紫，主要考察对级数求和公式的背诵。

不过除了我这个蒟蒻，大佬们应该都有实力在赛时发明公式。

为方便表示，比较长的整体在句子中用括号表示。

Sol

自然而然想到 dp。

考虑如何设计 dp 状态？

• 考虑逐层递推？
• 题目要求的是第 n 层最终透过了多少光。
• 光线会反复弹射，所以第 i 层的最终透光率和（光反射进入前一层然后弹射出来的占比）直接挂钩。

显而易见，可以设 f_i 表示前 i 层的透光率，g_i 表示从 i 层之后的空气中射入前 i 层，不考虑折射，然后反弹出来回到 i 层之后的空气中的光线占最初光纤的占比。

然后，分别计算。

• 对于 f_i，光纤来源是 f_{i-1}，每打中一次第 i 层玻璃，都有 \frac{a_i}{100} 的占比进入下一层，剩余 \frac{b_i}{100} \cdot g_{i-1} 的占比留到下一次打中第 i 层玻璃。
• 所以：f_i = \sum\limits_{p=0}^{\infty}{f_{i-1} \cdot \frac{a_i}{100} \cdot (\frac{b_i}{100} \cdot g_{i-1})^p}
• 对于 g_i，可以用类似方法简单推导得出以下结论。
• g_i = \frac{b_i}{100} + \sum\limits_{p=0}^{\infty}{\frac{a_i}{100} \cdot g_{i-1} \cdot (\frac{b_i}{100} \cdot g_{i-1})^p \cdot \frac{a_i}{100}}

可以发现 f_i,g_i 的计算，只要把多余项提出去，就变成了典型的指数级数，所以：

带入公式 \sum\limits_{k=0}^{\infty} x^k = \frac{1}{1-x} 直接算就行了。