题解 P1654 【OSU!】

· · 题解

有 (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;
  }