[BJOI2019]光线（DP）

降智了……

当你走头无路的时候就应该知道瞎搞一个DP：

$p[i]$ 表示光射入第 $1$ 块玻璃时，从第 $i$ 块玻璃出去的光量。

$q[i]$ 表示光射入第 $i$ 块玻璃时，从第 $i$ 块玻璃出去的光亮。

为什么是第 $i$ 块呢？因为我们最后只关注 $p[n]$，所以我们关注的反射都是前 $i$ 块射向第 $i+1$ 块（也就是 $q[i]$）和从第 $i+1$ 块射向前 $i$ 块（也就是 $b_{i+1}$）。

初始状态 $p[1]=a_1,q[1]=b_1$。答案为 $p[n]$。

随便画个图得到转移：

$$p[i]=\dfrac{p[i-1]a_i}{1-q[i-1]b_i}$$

$$q[i]=b_i+\dfrac{q[i-1]a_i^2}{1-q[i-1]b_i}$$

时间复杂度 $O(n\log)$。可以做到 $O(n)$，但是懒得写了。

#include<bits/stdc++.h>

using namespace std;

const int maxn=,mod=,inv100=;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,a[maxn],b[maxn],f[maxn],g[maxn];

inline int add(int x,int y){return x+y<mod?x+y:x+y-mod;}

inline int sub(int x,int y){return x<y?x-y+mod:x-y;}

inline int mul(int x,int y){return 1ll*x*y%mod;}

inline int qpow(int a,int b){

    int ans=;

    for(;b;b>>=,a=mul(a,a)) if(b&) ans=mul(ans,a);

    return ans;

}

int main(){

    n=read();

    FOR(i,,n) a[i]=mul(read(),inv100),b[i]=mul(read(),inv100);

    f[]=a[];g[]=b[];

    FOR(i,,n){

        int inv=qpow(sub(,mul(g[i-],b[i])),mod-);

        f[i]=mul(mul(f[i-],a[i]),inv);

        g[i]=add(b[i],mul(mul(mul(a[i],a[i]),g[i-]),inv));

    }

    printf("%d\n",f[n]);

}

巴特西

[BJOI2019]光线（DP）

最新文章

热门文章