算法1

(组合计数) $O(n)$

设有序列a1,a2,a3..an.
对于序列中任意数ai,i前面可以有0~i个数,i后面可以有0~n-i+1个数.注意:i前面或者后面都可以有0个数.
所以根据乘法原理,第i个数被计算了i*(n-i+1)次.由此,总和累加起来即可.

时间复杂度

O(n)

C++ 代码

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

using namespace std;

const int N=1e5+10;

long double a[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%Lf",&a[i]);

    long double sum=0;
    for(int i=1;i<=n;i++) 
    sum+=(long double)(i)*(n-i+1)*a[i];
      //a[i]前面的元素个数的方案*a[i]后面的元素个数的方案

   printf("%.2Lf",sum);
    return 0;
}