题目
https://www.luogu.org/problem/P1654
题意
给定每个位置为$1$的几率，一段长度为$x$的连续的并且极大的$1$对得分的贡献为$x^3$，求得分的期望。
题解
显然，我们可以换一种统计答案的方式，把贡献分给每个极长的前缀$1$，设在序列的第$i$个位置时，这个贡献为$val_i$。
当$i$前面有且仅有$x$个$1$时，$val_i=(x+1)^3-x^3=3x^2+3x+1$
答案式为$$sum_{A}(prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}sum_{k=1}^{n}{val_k})$$
对于长度为$i-1$的某个序列$A_0$，假设它对答案的贡献$$sum_{k=1}^{i-1}{val_k}=x$$
在其后再加一个$1$，对答案的贡献变为$p_isum_{k=1}^{i}{val_k}=p_i(x+val_i)$
在其后再加一个$0$，对答案的贡献变为$(1-p_i)sum_{k=1}^{i}{val_k}=(1-p_i)x$
所以，对答案的总贡献为$p_i(x+val_i)+(1-p_i)x=x+p_ival_i$
直观的理解是这样，但是对于不同的序列$A_x$，$val_i$都不一样，它们对答案的贡献都可以这样在一起转移吗？
是的。从答案式出发，对于长度为$l-1$的所有序列$A$，有
$$sum_{A}(prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}sum_{k=1}^{l-1}{val_k})$$
对于长度为$l$的所有序列$A'$，有
$$sum_{A'}(prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}sum_{k=1}^{l}{val_k})$$ $$=(sum_{A}prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}(sum_{k=1}^{l-1}{val_k}) + val_l)cdot p_l + sum_{A}(prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}sum_{k=1}^{l-1}{val_k}) cdot (1-p_l)$$ $$=sum_{A}(prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}sum_{k=1}^{l-1}{val_k}) + sum_{A}prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}{val_l} cdot p_l$$
我们发现$sum_{A}prod_{a_i=1}{p_i}prod_{a_j=0}{(1-p_j)}{val_l}$是一个很有意义的量，我们称之为期望，记做$v_l$。
现在我们再来算$v_l$，有$$v_l=sum_{x=0}^{l-1}{(1-p_{l-x-1})(3x^2+3x+1)prod_{k=1}^{x}{p_{l-k}}}$$
我们把这个和式拆成$3$部分，$sum_{x=0}^{l-1}{(1-p_{l-x-1})(3x^2)prod_{k=1}^{x}{p_{l-k}}}$，$sum_{x=0}^{l-1}{(1-p_{l-x-1})(3x)prod_{k=1}^{x}{p_{l-k}}}$，和$sum_{x=0}^{l-1}{(1-p_{l-x-1})1prod_{k=1}^{x}{p_{l-k}}}$
这种变换能够成立，我们称之为期望的线性性。
第三个式子最简单，不用算，它显然是$1$，因为期望是概率乘权值，当权值恒为$1$时，所有的概率加起来自然是$1$的。
对于第一个式子和第二个式子，我们把它的$3$提出来，即可用类似哈希的方法维护了。
具体来说，把式子用阶梯状的写出来，然后每次考虑括号内加增量，然后乘个$p_i$就好了（太麻烦，懒得写了）
因为所有的概率和为$1$，所以不用特殊考虑$(1-p_i)$（在加增量的时候考虑）
#include<cstdio> #include<cstring> #include<iostream> #define ri register int #define N 100050 using namespace std; double f1[N],f2[N],ans[N],p[N]; int n; int main() { scanf("%d",&n); for (ri i=1;i<=n;i++) scanf("%lf",&p[i]); for (ri i=1;i<=n;i++) { f1[i]=(f1[i-1]+1)*p[i]; f2[i]=(f2[i-1]+2*f1[i-1]+1)*p[i]; ans[i]=ans[i-1]+(3*f2[i-1]+3*f1[i-1]+1)*p[i]; } printf("%.1lf",ans[n]); return 0; }