题目：https://loj.ac/problem/3093
考虑经过种种反射，最终射下去的光线总和。往下的光线就是这个总和 * a[ i ] 。
比如只有两层的话，设射到第二层的光线是 lst ，那么 \( lst' = ( lst + lst*b[2]*b[1] + lst*(b[2]*b[1])^2 + ... )*a[2] \)
考虑令 f[ i ] 表示 “从第 i 层下面射上来的单位光线在考虑第 i+1 层反射的情况下射下去的值” 。
\( f[i] = b[i]+a[i]*f[i-1]*a[i] + ( b[i]+a[i]*f[i-1]*a[i] ) * b[i+1] * ( b[i]+a[i]*f[i-1]*a[i]) + ... \)
其中 \( b[i]+a[i]*f[i-1]*a[i] \) 就是一次反射下去的光线和。设 \( x = b[i]+a[i]*f[i-1]*a[i] \)
式子也就是 \( f[i]=x+x*b[i+1]*x + ... = x \sum\limits_{k=0}^{\infty}(b[i+1]*x)^k \)
然后令 lst 表示透过第 i-1 层的光线，lst' 表示透过第 i 层的光线，就有 \( lst' = (lst + lst*b[i]*f[i-1])*a[i] \)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=5e5+,mod=1e9+;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}
int pw(int x,int k)
{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;} int n,a[N],b[N],f[N],ans;
int main()
{
n=rdn(); int iv=pw(,mod-);
for(int i=;i<=n;i++)
{
a[i]=(ll)rdn()*iv%mod;
b[i]=(ll)rdn()*iv%mod;
}
for(int i=;i<=n;i++)
{
int x=(b[i]+(ll)a[i]*f[i-]%mod*a[i])%mod;
f[i]=(ll)x*pw(upt(-(ll)x*b[i+]%mod),mod-)%mod;
}
ans=a[];
for(int i=;i<=n;i++)
ans=(+(ll)b[i]*f[i-])%mod*ans%mod*a[i]%mod;
printf("%d\n",ans);
return ;
}