P5323 [BJOI2019] 光线
题目描述
当一束光打到一层玻璃上时，有一定比例的光会穿过这层玻璃，一定比例的光会被反射回去，剩下的光被玻璃吸收。
设对于任意 \(x\)，有 \(x \times a_i\%\) 单位的光会穿过它，有 \(x \times b_i\%\) 的会被反射回去。
现在 \(n\) 层玻璃叠在一起，有 \(1\) 单位的光打到第 \(1\) 层玻璃上，那么有多少单位的光能穿过所有 \(n\) 层玻璃呢？
数据范围：
对于 \(5\%\) 的数据，\(n=1\)；
对于 \(20\%\) 的数据，\(n\le 2\)；
对于 \(30\%\) 的数据，\(n\le 3\)；
对于 \(50\%\) 的数据，\(n\le 100\)；
对于 \(70\%\) 的数据，\(n\le 3000\)；
对于 \(100\%\) 的数据，\(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\) 在满足上述限制的整数中随机生成。
思路：
这个题目我们肯定能够想到一个异常简单的 \(dp\)
令 \(f_i\) 表示从 \(1\rightarrow i\) 透过光的数量，\(g_i\) 表示从 \(i\) 向后然后又回到 \(i\) 的光的数量。
则可以列出转移方程
然后我们先令 \(i=n\)，则
\[\left\{\begin{matrix} f_n=f_{n-1}\times a_n\\ g_n=f_{n-1}\times b_n\\ \end{matrix}\right. \]再令 \(i=n-1\)，则
\[\left\{\begin{matrix} f_{n-1}=f_{n-2}\times a_{n-1}+(f_{n-1}\times b_n)\times b_{n-1}\\ g_{n-1}=f_{n-2}\times b_{n-1}+(f_{n-1}\times b_n)\times a_{n-1} \end{matrix}\right. \]现在我们尝试化简上述的方程：
令 \(F_i=\frac{f_i}{f_{i-1}},G_i=\frac{g_i}{f_{i-1}}\)
则有：
由 ① 得：
\(F_i=a_i+G_{i+1}\times F_i\times b_i\Rightarrow F_i=\frac{a_i}{1-G_{i+1}\times b_i}\)
由 ② 得：
\(G_i=b_i+G_{i+1}\times F_i\times a_i\)
所以：
- \(F_i=\frac{a_i}{1-G_{i+1}\times b_i}\)
- \(G_i=b_i+G_{i+1}\times F_i\times a_i\)
然后我们再求原来的 \(f_i\)
\(f_i=f_{i-1}\times F_i\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls i<<1
#define rs i<<1|1
#define pb push_back
#define pt putchar
#define All(a) a.begin(),a.end()
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=5e5+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n;
int a[maxn],b[maxn];
int F[maxn],G[maxn];
int f[maxn];
int qp(int x,int k){
int res=1;
while(k){
if(k&1)res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
for(int i=1;i<=n;i++)a[i]=a[i]*qp(100,mod-2)%mod,b[i]=b[i]*qp(100,mod-2)%mod;
F[n]=a[n];
G[n]=b[n];
for(int i=n-1;i>=1;i--){
F[i]=a[i]*qp((1-G[i+1]*b[i]%mod+mod)%mod,mod-2)%mod;
G[i]=(G[i+1]*F[i]%mod*a[i]%mod+b[i])%mod;
}
f[0]=1;
for(int i=1;i<=n;i++)f[i]=f[i-1]*F[i]%mod;
cout<<f[n]<<endl;
return 0;
}