题目大意:有一束光线要依次穿过$n$块玻璃。

第i块玻璃的透射率为$a_i$,反射率为$b_i$。

问你有多少光能最终穿过所有玻璃。

数据范围:$n≤5\times 10^5$,答案对$998244353$取模。

我们考虑暴力把前$i-1$块玻璃看做一块玻璃,我们计算出了这块玻璃的透射率为$a$,反射率为$b$。

假设当前射过来的光线为$x$,第$i$块玻璃的透射率为$A$,反射率为$B$。

我们考虑强行打表:

第一次穿过玻璃i的光线量为$Ax$。

第二次为$ABbx$

第三次为$AB^2b^2x$

.....

以此类推。

考虑到$Bb$是小于$1$的,根据等比数列求和公式,最终能穿过玻璃$i$的光线总量为:

$X=xA\times\dfrac{Bb}{1-Bb}$

我们考虑如何更新$a$和$b$。

我们按照上面强行打表的方式打一个表,发现:

$newa=Aa\times\dfrac{Bb}{1-Bb}$

$newb=B+A^2b \times\dfrac{Bb}{1-Bb}$

直接处理就行了,复杂度$O(n\log MOD)$

 #include<bits/stdc++.h>
#define L long long
#define MOD 1000000007
#define I(x) pow_mod(x,MOD-2)
using namespace std;
L pow_mod(L x,L k){L ans=;for(;k;k>>=,x=x*x%MOD) if(k&) ans=ans*x%MOD; return ans;} int main(){
L a=,b=,x=,I100=I();
int n; cin>>n;
while(n--){
L A,B; scanf("%lld%lld",&A,&B);
A=A*I100%MOD; B=B*I100%MOD;
L Bb=B*b%MOD;
Bb=I(-Bb+MOD)%MOD;
x=x*A%MOD*Bb%MOD;
L newa=A*a%MOD*Bb%MOD;
L newb=(B+A*A%MOD*b%MOD*Bb)%MOD;
a=newa; b=newb;
}
cout<<x<<endl;
}
05-11 16:56
查看更多