题解 P1654 【OSU!】
ShineEternal
2019-08-17 18:40:34
节选自[vercont的洛谷日报](https://www.luogu.org/problemnew/solution/P1654)
## 题目链接：
https://www.luogu.org/problemnew/solution/P1654
## 分析：
我们可以观察到每次对答案的贡献是三次方级别的。
吼啊，我不会三次方期望啊。
仔细观察，首先发现一次方的期望是很好弄的。
于是设$a[i]$表示前i位中第i位为1的长度的期望：
则有
$$a[i]=(a[i-1]+1)\times p[i]$$
$tag$：即为在i-1的末尾加一个概率为$p[i]$出现的1
接着推平方
设$b[i]$表示前i位中第i位为1的长度的平方的期望：
则有
$$b[i]=(b[i-1]+2\times a[i-1]+1)\times p[i]$$
$tag$:期望的线性延伸：
$$x^2->(x+1)^2->x^2+2x+1$$
运用这种方法，我们可以在求出$a[i]$的基础上推出$b[i]$
同理，设$f[i]$表示前i位中第i位为1的长度的立方的期望：
则有：
$$f[i]=(f[i-1]+3\times b[i-1]+3\times a[i-1]+1)\times p[i]$$
- 哇塞我要A紫题了！！！
然后在满心欢喜的提交上去后发现wa了。
显然，我们还有没考虑到的地方？
是什么呢？
是最后求得的答案与中间过渡式子的不同性。
其实，前三个式子我们都只考虑**第i位**，这样做是为了递推下面的式子，但是答案让我们求出最终的期望分数，也就是**前n位**，这时输出f[n]自然就炸了。
所以，只需把三次方递推式稍微变形一下即可；
$$f[i]=(f[i-1]+3\times b[i-1]+3\times a[i-1]+1)\times p[i]+f[i-1]\times (1-p[i])=f[i-1]+(3\times b[i-1]+3\times a[i-1]+1)\times p[i]$$
这样最终的$f[n]$就是答案喽！
### code：
```cpp
//AC记录：https://www.luogu.org/record/21569138
#include<cstdio>
using namespace std;
double a[100005],b[100005],f[100005],p[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf",&p[i]);
a[i]=(a[i-1]+1)*p[i];
b[i]=(b[i-1]+2*a[i-1]+1)*p[i];
f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*p[i];
}
printf("%.1lf\n",f[n]);
return 0;
}
```
~~学好数学期望，递推AC紫题！(其实这应该算dp~~
$tag:$这题还可以扩展到k次，也就是$X^k$，用二项式定理$O(nk^2)$解决
觉得不够快？食用NTT对其加速可以达到$O(nklog_k)$