自动搬运

查看原文

来自洛谷，原作者为

	hall_of_history **

搬运于2025-08-24 21:27:34，当前版本为作者最后更新于2018-07-22 21:46:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有$(x+1)^3$

$=(x+1)*(x+1)*(x+1)$

$=(x^2+2*x+1)*(x+1)$

$=x^3+2*x^2+x+x^2+2*x+1$

$=x^3+3*x^2+3*x+1;$

每多增加一个1，使答案变成$x^3+3*x^2+3*x+1,$

与原答案相比多了$3*x^2+3*x+1,$

维护这个增加值的期望

维护$x1[i]$表示$x$的期望;

维护$x2[i]$表示$x^2$的期望

$x1[i]=(x1[i-1]+1)*p[i];$

$x2[i]=(x2[i-1]+2*x1[i-1]+1)*p[i];$

那么 $ans[i]=ans[i-1]+(3*x2[i-1]+3*x1[i-1]+1)*p[i];$

最终答案就是$ans[n].$

代码：

  #include<cstdio>
  #include<cstring>
  #include<iostream>
  #include<algorithm>

  #define maxn 111111
  #define int long long
  using namespace std;

  int n;
  double p[maxn];
  double x1[maxn],x2[maxn],ans[maxn];

  signed main()
  {
      scanf("%lld",&n);
      for(int i=1;i<=n;i++)
          scanf("%lf",&p[i]);
      for(int i=1;i<=n;i++){
          x1[i]=(x1[i-1]+1)*p[i];
          x2[i]=(x2[i-1]+2*x1[i-1]+1)*p[i];
          ans[i]=ans[i-1]+(3*(x1[i-1]+x2[i-1])+1)*p[i];
      }
      printf("%.1lf",ans[n]);
      return 0;
  }