[洛谷 5323][BJOI2019]光线

题目链接

https://www.luogu.org/problemnew/show/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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注