题解 P5323 【[BJOI2019]光线】

· · 题解

来提供一个似乎题解里面还没有的做法。

首先考虑设f[i]为假设有1单位的光线从上到下射到第i层玻璃，最后会有多少光线穿过第i层玻璃。那么答案显然是\prod f[i]。

然后发现有在第i层这里反射的，而反射的又不好直接算，那怎么办呢？

考虑再设一个g[i]表示前i层的玻璃，从下到上射1单位的光线，最后有多少会被反射回来。

考虑转移：

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

首先f的转移。a_i是直接穿过的，b_i是反射回来的，那么b_i\times g[i-1]就是再回去的光线，再\times f[i]就是最后穿过的光线了。

然后g的转移。b_i是直接反射的，a_i是穿过去了的，那么a_i\times g[i-1]就是再打回来的，再\times f[i]就也是穿过的光线了。

显然f[i]能由g[i-1]推出，g[i]能由f[i],g[i-1]推出。

这样就做完了，复杂度O(n\log n).

实际上推完式子可以发现，f不需要g也能转移，但是两个都在还是意义更加清晰明了。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#define eps 1e-15
#define maxn 500010
#define maxm 410
#define inf 999999999999999
#define mod 1000000007
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int>pii;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int quick_pow(int x,int p)
{
    int an=1,po=x;
    while(p)
    {
        if(p&1)  an=1ll*an*po%mod;
        po=1ll*po*po%mod;
        p>>=1;
    }
    return an;
}
int a[maxn],b[maxn];
int f[maxn],g[maxn];
int main()
{
    n=read();
    int INV=quick_pow(100,mod-2);
    for(int i=1;i<=n;i++)  a[i]=1ll*read()*INV%mod,b[i]=1ll*read()*INV%mod;
    f[1]=a[1];g[1]=b[1];
    for(int i=2;i<=n;i++)
    {
        int tmp=(mod+1-1ll*b[i]*g[i-1]%mod+mod)%mod;
        tmp=quick_pow(tmp,mod-2);f[i]=1ll*tmp*a[i]%mod;
        g[i]=(b[i]+1ll*g[i-1]*a[i]%mod*f[i]%mod)%mod;
    }
    int ans=1;
    for(int i=1;i<=n;i++)  ans=1ll*ans*f[i]%mod;
    cout<<ans<<endl;
    return 0;
}