LOJ#3093. 「BJOI2019」光线（递推+概率期望）

迈不过友情╰ 2021-12-23 05:47 166阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

把\\(a\_i\\)和\\(b\_i\\)都变成小数的形式，记\\(f\_i\\)表示\\(1\\)单位的光打到第\\(i\\)个玻璃上，能从第\\(n\\)个玻璃下面出来的光有多少，记\\(g\_i\\)表示能从第\\(i\\)块玻璃反射出来的光有多少，，递推式的话，我们枚举一下这束光在\\(i\\)和\\(i+1\\)块玻璃之间反射了几次就可以了

\\\[ \\begin\{aligned\} f\_i &=a\_i\\left(f\_\{i+1\}+g\_\{i+1\}\\times b\_i\\times f\_\{i+1\}+g\_\{i+1\}\\times b\_i\\times g\_\{i+1\}\\times b\_i\\times f\_\{i+1\}+...\\right)\\\\ &=a\_if\_\{i+1\}\\sum\\limits\_\{k=0\}^\\infty (b\_i\\times g\_\{i+1\})^k\\\\ &=a\_if\_\{i+1\}\{1\\over 1-b\_i\\times g\_\{i+1\}\}\\\\ g\_i &=b\_i+a\_ig\_\{i+1\}a\_i+a\_ig\_\{i+1\}b\_ig\_\{i+1\}a\_i+...\\\\ &=b\_i+a\_i^2g\_i\\sum\\limits\_\{k=0\}^\\infty (b\_i\\times g\_\{i+1\})^k\\\\ &=b\_i+a\_i^2g\_\{i+1\}\{1\\over 1-b\_ig\_\{i+1\}\} \\end\{aligned\} \\\]

然而问题来了，如果\\(b\_i=0\\)的特殊情况该怎么办？

我们发现在这种情况下，手玩出来的和代入柿子计算的值似乎是一样的？

所以直接代入柿子并没有问题的说……

递推即可

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define inline __inline__ __attribute__((always_inline))
    #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
    #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
    template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
    using namespace std;
    char buf[1<<21],*p1=buf,*p2=buf;
    inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    int read(){
        R int res,f=1;R char ch;
        while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    const int N=5e5+5,P=1e9+7,inv=570000004;
    inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
    inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
    inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
    int ksm(R int x,R int y){
        R int res=1;
        for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
        return res;
    }
    int a[N],b[N],f[N],g[N],res,n,tmp;
    int main(){
    //  freopen("testdata.in","r",stdin);
        n=read();
        fp(i,1,n)a[i]=read(),b[i]=read(),a[i]=mul(a[i],inv),b[i]=mul(b[i],inv);
        f[n]=a[n],g[n]=b[n];
        fd(i,n-1,1){
            tmp=ksm(P+1-mul(g[i+1],b[i]),P-2);
            f[i]=1ll*a[i]*f[i+1]%P*tmp%P;
            g[i]=add(b[i],1ll*a[i]*a[i]%P*g[i+1]%P*tmp%P);
        }
        printf("%d\n",f[1]);
        return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10754755.html

[Link 1]: https://loj.ac/problem/3093