Loj #3093. 「BJOI2019」光线
题目描述
当一束光打到一层玻璃上时,有一定比例的光会穿过这层玻璃,一定比例的光会被反射回去,剩下的光被玻璃吸收。
设对于任意 \(x\),有 \(x\times a_i\%\) 单位的光会穿过它,有 \(x\times b_i\%\) 的会被反射回去。
现在 \(n\) 层玻璃叠在一起,有 \(1\) 单位的光打到第 \(1\) 层玻璃上,那么有多少单位的光能穿过所有 \(n\) 层玻璃呢?
输入格式
第一行一个正整数 \(n\),表示玻璃层数。
接下来 \(n\) 行,每行两个非负整数 \(a_i,b_i\),表示第 \(i\) 层玻璃的透光率和反射率。
输出格式
输出一行一个整数,表示穿透所有玻璃的光对 \(10^9 + 7\) 取模的结果。
可以证明,答案一定为有理数。设答案为 \(a/b\)(\(a\) 和 \(b\) 是互质的正整数),你输出的答案为 \(x\),你需要保证 \(a\equiv bx \pmod {10^9 + 7}\)。
数据范围与提示
对于 \(5\%\) 的数据,保证 \(n=1\)。
对于 \(20\%\) 的数据,保证 \(n\le 2\)。
对于 \(30\%\)的数据,保证 \(n\le 3\)。
对于 \(50\%\) 的数据,保证 \(n\le 100\)。
对于 \(70\%\) 的数据,保证 \(n\le 3000\)。
对于 \(100\%\) 的数据:
- \(1\le n\le 5\times 10^5\)
- \(1\le a_i \le 100\)
- \(0\le b_i \le 99\)
- \(1\le a_i+b_i \le 100\)
- 每组 \(a_i\) 和 \(b_i\) 在满足上述限制的整数中随机生成。
\(\\\)
设\(f_i\)表示一单位光从上至下打到第\(i\)块玻璃之后能穿过第\(n\)块玻璃的单位数量。
\(g_i\)表示一单位光从下至上打到第\(i\)块玻璃之后能穿过第\(n\)块玻璃的单位数量。
特别地\(g_0=0,f_{n+1}=1\)。
于是我们容易得到:
\Rightarrow f_{i+1}=\frac{f_i-b_i\%g_{i-1}}{a_i\%}\\
\]
这里不需要考虑\(a_i=0\)的问题,因为\(a_i=0\)时答案为\(0\),特判掉就好了。
以及:
\]
我们可以设\(f_1=x\),然后按照上面两个\(DP\)出\(f_{n+1}\)用\(x\)表示时的系数。答案就是\(\frac{1}{f_{n+1}}\)。
代码:
#include<bits/stdc++.h>
#define ll long long
#define N 500005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=1e9+7;
ll ksm(ll t,ll x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
int n;
ll a[N],b[N];
const ll inv100=ksm(100,mod-2);
ll f[N],g[N];
int main() {
n=Get();
for(int i=1;i<=n;i++) {
a[i]=inv100*Get()%mod,b[i]=inv100*Get()%mod;
}
for(int i=1;i<=n;i++) {
if(a[i]==0) {cout<<0;return 0;}
}
f[1]=1;
f[2]=ksm(a[1],mod-2);
g[1]=b[1]*f[2]%mod;
for(int i=2;i<=n;i++) {
f[i+1]=(f[i]-b[i]*g[i-1]%mod+mod)*ksm(a[i],mod-2)%mod;
g[i]=(a[i]*g[i-1]+b[i]*f[i+1])%mod;
}
cout<<ksm(f[n+1],mod-2);
return 0;
}