Loj #3093. 「BJOI2019」光线

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\)。

于是我们容易得到:

\[f_i=a_i\%f_{i+1}+b_i\%g_{i-1}\ (1\leq i\leq n)\\
\Rightarrow f_{i+1}=\frac{f_i-b_i\%g_{i-1}}{a_i\%}\\
\]

这里不需要考虑\(a_i=0\)的问题,因为\(a_i=0\)时答案为\(0\),特判掉就好了。

以及:

\[g_i=a_i\% *g_{i-1}+b_i\% *f_{i+1}\ (1\leq i\leq n)\\
\]

我们可以设\(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;
}
上一篇:ElasticSearch基本概念


下一篇:js---BOM