题面
题解
把(a_i)和(b_i)都变成小数的形式,记(f_i)表示(1)单位的光打到第(i)个玻璃上,能从第(n)个玻璃下面出来的光有多少,记(g_i)表示能从第(i)块玻璃反射出来的光有多少,,递推式的话,我们枚举一下这束光在(i)和(i+1)块玻璃之间反射了几次就可以了
[egin{aligned}
f_i
&=a_ileft(f_{i+1}+g_{i+1} imes b_i imes f_{i+1}+g_{i+1} imes b_i imes g_{i+1} imes b_i imes f_{i+1}+...
ight)\
&=a_if_{i+1}sumlimits_{k=0}^infty (b_i imes g_{i+1})^k\
&=a_if_{i+1}{1over 1-b_i imes g_{i+1}}\
g_i
&=b_i+a_ig_{i+1}a_i+a_ig_{i+1}b_ig_{i+1}a_i+...\
&=b_i+a_i^2g_isumlimits_{k=0}^infty (b_i imes g_{i+1})^k\
&=b_i+a_i^2g_{i+1}{1over 1-b_ig_{i+1}}
end{aligned}
]
然而问题来了,如果(b_i=0)的特殊情况该怎么办?
我们发现在这种情况下,手玩出来的和代入柿子计算的值似乎是一样的?
所以直接代入柿子并没有问题的说……
递推即可
//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=5e5+5,P=1e9+7,inv=570000004;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
R int res=1;
for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
return res;
}
int a[N],b[N],f[N],g[N],res,n,tmp;
int main(){
// freopen("testdata.in","r",stdin);
n=read();
fp(i,1,n)a[i]=read(),b[i]=read(),a[i]=mul(a[i],inv),b[i]=mul(b[i],inv);
f[n]=a[n],g[n]=b[n];
fd(i,n-1,1){
tmp=ksm(P+1-mul(g[i+1],b[i]),P-2);
f[i]=1ll*a[i]*f[i+1]%P*tmp%P;
g[i]=add(b[i],1ll*a[i]*a[i]%P*g[i+1]%P*tmp%P);
}
printf("%d
",f[1]);
return 0;
}