P5323 BJOI2019 光线

主要详细写写系数怎么暴力化开。

光线视作从左射入,从右射出。

设 $L_i,R_i$ 为 所有 从第 $i$ 块玻璃向左和向右射出的光线数量。

那么显然有

$$ \begin{align} R_i=a_i·R_{i-1}+b_i·L_{i+1}\\ L_i=b_i·R_{i-1}+a_i·L_{i+1} \end{align} $$

特殊地,对于第 $n$ 个位置,我们还有

$$ \begin{aligned} R_n=a_n·R_{n-1}\\ L_n=b_n·R_{n-1} \end{aligned} $$

可以发现貌似 $R_i$ 和 $L_i$ 都可以用 $R_{i-1}$ 来表示,于是就考虑设 $L_i=A_i·R_{i-1},R_i=B_i·R_{i-1}$ 。

于是瞄一眼数据范围,思考怎么递推系数。初始我们有 $A_n=b_n,B_n=a_n$ 。

$$ \begin{aligned} R_i&=a_i·R_{i-1}+b_i·L_{i+1}\\ R_i&=a_i·R_{i-1}+b_i·A_{i+1}·R_i\\ (1-b_i·A_{i+1})R_i&=a_i·R_{i-1}\\ R_i&=\frac{a_i}{1-b_i·A_{i+1}}·R_{i-1}\\ ∴B_i&=\frac{a_i}{1-b_i·A_{i+1}}\\ L_i&=b_i·R_{i-1}+a_i·A_{i+1}·R_i\\ L_i&=b_i·R_{i-1}+a_i·A_{i+1}·B_i·R_{i-1}\\ L_i&=(b_i+a_i·A_{i+1}·B_i)·R_{i-1}\\ ∴A_i&=b_i+a_i·A_{i+1}·B_i\\ \end{aligned} $$

最后 $Ans=\prod_{i=1}^nB_i$ 。

code:

#include<bits/stdc++.h>
#define reg register
#define For(i,a,b) for(reg int i=(a),i##END=(b);i<=i##END;i++)
#define int long long
using namespace std;
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
const int mod=1e9+7;
int inv(int a,int b=mod-2){
    int x=1;
    while(b){
        if(b&1)(x*=a)%=mod;
        (a*=a)%=mod,b>>=1;
    }
    return x;
}
const int N=5e5+10;
int a[N],b[N],A[N],B[N];
signed main(){
    int inv100=inv(100);
    int n=read();
    For(i,1,n)a[i]=read()*inv100%mod,b[i]=read()*inv100%mod;
    A[n]=b[n],B[n]=a[n];
    for(int i=n-1;i>=1;i--)
        B[i]=a[i]*inv((mod+1-b[i]*A[i+1]%mod)%mod)%mod,
        A[i]=a[i]*A[i+1]%mod*B[i]%mod+b[i],A[i]%=mod;
    int ans=1;
    For(i,1,n)ans=ans*B[i]%mod;
    printf("%lld\n",ans);
    return 0;
}
最后修改:2021 年 03 月 25 日
如果觉得我的文章对你有用,请随意赞赏