0%

LOJ3093 「BJOI2019」光线

my submission on loj.ac

设 $f_i$ 表示从第 $i-1$ 块玻璃和第 $i$ 块玻璃之间向第 $n$ 块玻璃的方向射出了一束大小为 $1$ 的光线,最终能穿过第 $n$ 层玻璃的光的数量。特别地,$f_{n+1} = 1$,你可以想象成在第 $n$ 块玻璃的后面还有一块反射率为 $0\%$、透光率为 $100\%$ 的玻璃。

下文中的 $a_i,b_i$ 为原题中的 $a_i\%, b_i\%$。

根据定义有

移项得

这样等号右边的项下标都小于等于 $i$。

设 $f_1 = x$,则所有的 $f_i$ 都可以用上面的递推式表示成 $kx$ 的形式。最后由 $f_{n+1} = 1$ 就可以解出 $x$ 的取值。

优化递推:设 $s_i = b_{i-1}f_i + a_{i-1}b_{i-2}f_{i-1} + a_{i-1}a_{i-2}b_{i-3}f_{i-2}+\cdots$,那么

时间复杂度为 $O(n)$ 或者 $O(n\log n)$,瓶颈为求逆元。