[洛谷 5323][BJOI2019]光线

题目链接

https://www.luogu.org/problem/P5323

题解

这可以说是一道非常不错的物理题。

玻璃有很多块，我们考虑从上往下合并玻璃，并求出合并后的玻璃的透光率和和反射率。

将第 \(1\) 至第 \(i\) 层玻璃经过合并后的玻璃的透光率和反射率分别记为 \(p_i,q_i\)。

可以推出：

$$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$$

显然 \(q_{i-1}b_i < 1\)，那么这个无穷级数就是收敛的。根据数学知识，我们推出：

$$\sum_{k=0}^{\infty}(q_{i-1}b_i)^k = \frac{1}{1-q_{i-1}b_i}$$

也即：

$$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}$$

这样本题就可以通过线性递推解决了（当然，因为求逆元需要 \(\log n\) 的时间，总时间复杂度是 \(O(n \log n)\)）。

#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
long long fpow(long long a,long long b)
{
 long long ans=1;
 while(b)
 {
  if(b&1)ans=ans*a%MOD;
  a=a*a%MOD;
  b>>=1;
 }
 return ans;
}
int main()
{
 long long n,p=1,q=0;
 cin>>n;
 long long inv100=fpow(100,MOD-2);
 for(int i=1;i<=n;i++)
 {
  long long a,b;
  cin>>a>>b;
  a=a*inv100%MOD;
  b=b*inv100%MOD;
  long long x=fpow((1-q*b%MOD+MOD)%MOD,MOD-2);
  p=p*a%MOD*x%MOD;
  q=(b+a*a%MOD*q%MOD*x%MOD)%MOD;
 }
 cout<<p<<endl;
 return 0;
}