题解 P1654 【OSU!】

· · 题解

节选自vercont的洛谷日报

题目链接：

https://www.luogu.org/problemnew/solution/P1654

分析：

我们可以观察到每次对答案的贡献是三次方级别的。

吼啊，我不会三次方期望啊。

仔细观察，首先发现一次方的期望是很好弄的。

于是设a[i]表示前i位中第i位为1的长度的期望：

则有

a[i]=(a[i-1]+1)\times p[i] 接着推平方 设$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]

然后在满心欢喜的提交上去后发现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：

//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

觉得不够快？食用NTT对其加速可以达到$O(nklog_k)