自动搬运

查看原文

来自洛谷，原作者为

	hhoppitree 成功的秘诀只有一个：加训。故古语有云：日拱一卒，功不唐捐；玉汝于成，溪达四海。

搬运于2025-08-24 22:16:45，当前版本为作者最后更新于2021-01-08 13:24:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意简述：

求一个期望，经过转化，发现，也就是求：

$$\sum_{1\le l\le r\le n}a^{r-l}(1-p_{l-1})(1-p_{r+1})\prod\limits_{i=l}^{r}p_i\sum\limits_{i=l}^{r}w_i $$

题目解法：

首先，本题解并不是一篇普通的题解，这是一篇 卡常题解。

做法推荐看 大佬 $\rm z7z-Eta$ 的，本文也是采用 TA 这种做法。

算是对这篇题解的补充吧。

我们发现，在这位大神的题解里，TA 开了许多数组，实际上只要开 $w$ 这一个数组就行了，如果改一改输入格式甚至空间复杂度能做到 $\mathcal{O}(1)$ 的（$w$ 只是个存数据的工具数组）正解：用修改输入文件格式让输入文件成为工具人。

具体点，在 TA 的题解中，递推式要维护数组 $t$ 和 $f$，但这两个数组递推维护一下就行了。

然后还要用到 $p_{i-1},p_{i},p_{i+1}$，滚动数组一下就行了，具体见代码。

然后就最优解了（截止本文写作日期 $[2021/1/8]$）（包括空间吧）。

然后就没有然后了。

还是看代码吧。

哦，如果您要问快的原因，过多的数组调用需要耗费时间。

顺便说些小细节：不要用 $\rm cin$，读入 $w_i$ 时不要手滑用 $\rm \%lf$（我开始就是这样所以速度只有 $\rm rank\;2$，后来看了 $\rm rank\;1$ 的代码才发现，这说明 $\rm \%lf$ 比少开数组重要）

正确代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int res=0;
	bool zf=0;
	char c;
	while(((c=getchar())<'0'||c>'9')&&c!='-');
	if(c=='-')zf=1;
	else res=c-'0';
	while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
	if(zf)return -res;
	return res;
}
int w[100005];
signed main(){
	int n=read();
	double a,b;
	scanf("%lf%lf",&a,&b);
	a=pow(a,b);
	double ans=0,t=0,f=0,p1=0.0,p2,p3;
	for(register int i=1;i<=n;++i){
		scanf("%d",&w[i]);
	}
	scanf("%lf",&p2);
	for(register int i=1;i<=n;++i){
		if(i!=n)scanf("%lf",&p3);else p3=0;
		t=a*p2*t+p2*(1-p1);
		f=a*p2*f+t*w[i];
		ans+=(1-p3)*f;
		p1=p2;p2=p3;
	}
	printf("%lf\n",ans);
	return 0;
}

最后，还是那句话：

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 $\text{OIer}$。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 $\text{OIer}$。