博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[BJOI2019] 光线
阅读量:7045 次
发布时间:2019-06-28

本文共 2061 字,大约阅读时间需要 6 分钟。

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

以下设:$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
#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
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
il void output(T x){
if(x/10)output(x/10);putchar(x%10+'0');}template
il void ot(T x){
if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
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<

 

转载于:https://www.cnblogs.com/Miracevin/p/10762667.html

你可能感兴趣的文章
DotLiquid模板引擎简介
查看>>
5.Flask-Migrate
查看>>
c# 正则表代式的分组和批评模式 .
查看>>
编程之美-3.1-字符串移位包含的问题
查看>>
EPC是什么
查看>>
T-SQL查询进阶--数据集之间的运算
查看>>
【Vegas原创】Linux下unrar安装与配置
查看>>
HDOJ 2095(找出唯一的出现一次的数)
查看>>
java面试32问
查看>>
钟翔平:坚持走手机浏览器架构创新之路
查看>>
图片处理--浮雕特效
查看>>
chr() ord() 的用法
查看>>
C++对象模型简介(二)——深入底层,探索本质
查看>>
Nginx模块之————RTMP模块的FFmpeg的配置问题是FFmpeg的连续退出
查看>>
基本的RAID介绍
查看>>
服务信息块协议 SMB(Server Message Block protocol)
查看>>
QM、艾瑞力证ofo远甩摩拜稳居行业第一 数据与技术“双杀”
查看>>
重庆健全养老服务体系 2018年新增社区养老服务站200所
查看>>
2018年贵州各项存款增速回落明显 贷款增速居全国第一
查看>>
一团伙在列车上利用“斗地主”诈骗 作案313起涉案42万
查看>>