本文最后更新于:2020年4月11日 下午

题目简述

  • 在初始状态下,您可以在T秒内每秒获得一个正常的Cookie。

  • 在这里,出现金色的cookie,其概率为每秒$P$个。

  • 金饼干以N种方式之一出现,每种方式的概率为$Q [i]$。

  • 当获取第i个金色cookie时,此后在$t [i]$秒内获得的正常cookie的放大倍数变为$x [i]$倍。

  • 每个黄金曲奇的效果都会成倍增加。

  • 在$T$秒内获得的cookie总数的期望值是多少?

题目分析

最终答案很大,小于$10 ^ {100}$,但是所需的精度很低,因此可以加倍计算。

由于double可以上升到$10 ^ {308}$,因此不会溢出。

如果在特定时间出现或不出现金色曲奇,则确定p秒后的放大倍率M [p]
一秒钟后,M [1] =(1-P)+ P *(x [0] * Q [0] + x [1] * Q [1] + ... + x [N-1] * Q [N-1])
当金色小甜饼的类型以t [i]的升序排序时,i是满足t [i] <x的最大i

P *(Q [0] + ... + Q [i])+ P *(x [i + 1] * Q [i +1] + ... + x [N-1] * Q [N-1])

请注意,答案的输出格式是特殊的。

核心部分伪代码


int T,N;
double P;
pair<int,pair<int,double> > E[1000001];
double TM[100001],TMm[100001];

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	cin>>T>>N>>P;
	FOR(i,N) cin>>E[i].second.second>>E[i].second.first>>E[i].first;
	sort(E,E+N);
	
	// TM後の枚数
	TM[1]=1-P;
	FOR(i,N) TM[1]+=P*E[i].second.second*E[i].second.first;
	j=0;
	for(i=2;i<=T;i++) {
		TM[i]=TM[i-1];
		while(j<N && E[j].first < i) {
			TM[i]-=P*E[j].second.second*E[j].second.first;
			TM[i]+=P*E[j].second.second;
			j++;
		}
	}
	
	TMm[0]=TM[0]=1;
	for(i=1;i<=T;i++) TMm[i]=TMm[i-1]*TM[i];
	
	double res=0;
	FOR(i,T) res += TMm[i];
	
	if(res>1e8) {
		int nu=0;
		while(res>1e8) res/=10.0,nu++;
		_P("%d",(int)res);
		FOR(i,nu) _P("0");
		_P("\n");
	}
	else {
		_P("%.8lf\n",res);
	}
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT697 【フィボナッチ】 上一篇
hexo博客【NexT从主题下载到随心DIY】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。