题解 P5323 【[BJOI2019] 光线】
小粉兔
2019-04-22 02:13:00
在博客园食用更佳：[https://www.cnblogs.com/PinkRabbit/p/BJOI2019D2T2.html](https://www.cnblogs.com/PinkRabbit/p/BJOI2019D2T2.html)
### 题意简述：
有 $n$ 面玻璃，第 $i$ 面的透光率为 $a$，反射率为 $b$。
问把这 $n$ 面玻璃按顺序叠在一起后，$n$ 层玻璃的透光率。
$0 < a_i \le 1$，$0 \le b_i < 1$。
### 题解：
题目中告诉我们，$n$ 层的玻璃也有透光率，换句话说，多层的玻璃可能可以看作一层。
从这个角度思考，考虑已经求出了前 $i - 1$ 层玻璃的透光率，如何求出前 $i$ 层玻璃的透光率。
可以发现已知透光率并不足以进一步求出新的透光率，我们似乎还需要知道反射率。
这时，如果你天真地认为反射率就是从第一面玻璃射入的光的反射率，你就错了。
需要特别注意的是，从第一面和最后一面射入的光的反射率是不相同的。
这是一个很大的坑点，如果注意到了这题就容易了；没注意到就会一直挠头。
总之，我们需要维护两个量：
1. 前 $i$ 面玻璃按顺序叠在一起后，光从**第 $1$ 面玻璃**射入时的透光率。
2. 前 $i$ 面玻璃按顺序叠在一起后，光从**第 $i$ 面玻璃**射入时的反射率。
分别记为 $P_i$ 和 $Q_i$，则不难推出：
$$\begin{aligned}P_i&=P_{i-1}a_i\sum_{k=0}^{\infty}(Q_{i-1}b_i)^k\\Q_i&=b_i+Q_{i-1}a_i^2\sum_{k=0}^{\infty}(Q_{i-1}b_i)^k\end{aligned}$$
其中我们发现带有 $\sum_{k=0}^{\infty}a^k$ 的形式，当 $|a|<1$ 时，这个无穷级数等于 $\frac{1}{1-a}$。
所以得到最终的递推式：
$$\begin{aligned}P_i&=\frac{P_{i-1}a_i}{1-Q_{i-1}b_i}\\Q_i&=b_i+\frac{Q_{i-1}a_i^2}{1-Q_{i-1}b_i}\end{aligned}$$
先算出 $\frac{1}{1-Q_{i-1}b_i}$ 可以简化计算。
代码如下：
```cpp
#include <cstdio>
typedef long long LL;
const int Mod = 1000000007;
const int Inv100 = 570000004;
inline LL Inv(LL b) {
LL a = 1;
for (int e = Mod - 2; e; e >>= 1, b = b * b % Mod)
if (e & 1) a = a * b % Mod;
return a;
}
int N;
LL P, Q;
int main() {
scanf("%d", &N);
P = 1, Q = 0;
while (N--) {
LL a, b;
scanf("%lld%lld", &a, &b);
a = a * Inv100 % Mod, b = b * Inv100 % Mod;
LL W = Inv((1 - Q * b % Mod + Mod) % Mod);
Q = (b + a * a % Mod * Q % Mod * W) % Mod;
P = P * a % Mod * W % Mod;
}
printf("%lld\n", P);
return 0;
}
```
题外话：你或许会想，既然反射率不同，透光率是否也不同呢？
然而经过计算，可以得到在每面玻璃两侧的透光率分别相同的情况下，最终两侧的透光率也相同。
这引出了一个有趣的光学原理：可以通过叠加不同的普通玻璃创造出两侧反射率不同的复合玻璃，但是透光率却始终相同。
同时也说明了毛玻璃并不是普通玻璃组合而成的。