枫林晚 的博客

枫林晚 的博客

题解 P5323 【[BJOI2019] 光线】

posted on 2019-04-24 15:30:33 | under 题解 |

戳我

看起来很麻烦,做起来并不难的题

以下设:$a_i=\frac{a_i}{100},b_i=\frac{b_i}{100}$

显然,如果$b_i=0$的话,直接求$\Pi a_i$就是答案。

解决反射问题是这个问题的关键

我们显然可以认为一束光透过之后,可以等其他的光一起 透过干净 再往后走。

这样就存在Dp的阶段了。

网上很多从“前i个整体透光率”“整体反光率”什么的,或者枚举反射次数,还要等比数列求和。其实不用这么麻烦。

设$f[i][1]$表示,一单位的光从玻璃i左边射过来,最终透过的比率

$f[i][2]$表示,一单位的光从玻璃i右边设过来,最终反射回来的比率

(最终就是经过相当长的一段时间后累计的总和。)

递推式很显然了,只要枚举“回收”光线的情况

$f[i][1]=a_i+b_i\times f[i-1][2] \times f[i][1]$

移项,除过去,可以得到:

$f[i][1]=\frac{a_i}{1-b_i\times f[i-1][2]}$

以及:

$f[i][2]=b_i+a_i\times f[i-1][2] \times f[i][1]$

发现存在边界:$f[1][1]=a_1,f[1][2]=b_1$

然后递推。

最后求$\Pi f[i][1]$即可得到答案

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Miracle{
const int N=5e5+5;
const int mod=1e9+7;
int n;
int iv;
int a[N],b[N];
int ad(int x,int y){
    return x+y>=mod?x+y-mod:x+y;
}
int qm(int x,int y){
    int ret=1;
    while(y){
        if(y&1) ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;
        y>>=1;
    }
    return ret;
}
int f[N][3];
int main(){
    iv=qm(100,mod-2);
    rd(n);
    for(reg i=1;i<=n;++i){
        rd(a[i]);rd(b[i]);
        a[i]=(ll)a[i]*iv%mod;
        b[i]=(ll)b[i]*iv%mod;
    }
    f[1][1]=a[1];
    f[1][2]=b[1];
    for(reg i=2;i<=n;++i){
        f[i][1]=(ll)a[i]*qm(ad(1,mod-(ll)b[i]*f[i-1][2]%mod),mod-2)%mod;
        f[i][2]=ad(b[i],(ll)a[i]*f[i-1][2]%mod*f[i][1]%mod);
    }
    int ans=1;
    for(reg i=1;i<=n;++i){
        ans=(ll)ans*f[i][1]%mod;
    }
    cout<<ans;
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
*/